Vue的虚拟DOM与diff算法学习笔记

什么是虚拟DOM和diff算法

在前端发展的初期,前端工程师们使用JQ这样的框架对DOM进行命令式的操作,这种方式最大的好处是易学,直白,但在前端页面和业务逻辑不断复杂的今天,命令式的操作dom已经不适合大型项目的开发,随之而来的三大框架,vue,react, angular均使用了声明式的操作DOM,开发者只要描述状态和和DOM的映射关系,框架就会帮我们把状态转化成渲染好的视图,虚拟DOM正是状态和真实DOM之间的一个中间层,为什么要有这个中间层呢,因为操作DOM的代价是非常大的,虚拟DOM可以描述描述真实dom的信息,通过对比前后的虚拟dom找出DOM里真正需要的部分,从而减少DOM操作,提高性能。比较前后虚拟dom的算法就是diff算法,这是整个虚拟dom机制的最核心优化之一。

VNode

VNode本质上是一个JS对象,只是这个对象是用来描述真实DOM而已,Vue的实现如下。( 函数参数里的 ?: 的意思是,这个参数可以没有,但是如果有的话就要是某个指定的类型,这是flow的语法)


export default class VNode {
  constructor (
    tag?: string,
    data?: VNodeData,
    children?: ?Array,
    text?: string,
    elm?: Node,
    context?: Component,
    componentOptions?: VNodeComponentOptions,
    asyncFactory?: Function
  ) {
    this.tag = tag //标签属性
    this.data = data  //渲染成真实DOM后,节点上到class attr style 事件等...
    this.children = children //子节点,也上vnode
    this.text = text  // 文本
    this.elm = elm  //对应着真实的dom节点
    this.ns = undefined //当前节点的namespace(命名空间)
    this.context = context //编译的作用域
    this.fnContext = undefined // 函数化组件上下文
    this.fnOptions = undefined // 函数化组件配置项
    this.fnScopeId = undefined // 函数化组件ScopeId
    this.key = data && data.key  //只有绑定数据下存在,在diff的过程中可以提高性能
    this.componentOptions = componentOptions // 通过vue组件生成的vnode对象,若是普通dom生成的vnode,则此值为空
    this.componentInstance = undefined  //当前组件实例
    this.parent = undefined // vnode、组件的占位节点
    this.raw = false    //是否为原生HTML或只是普通文本
    this.isStatic = false  //静态节点标识 || keep-alive
    this.isRootInsert = true    // 是否作为根节点插入
    this.isComment = false  // 是否为注释节点
    this.isCloned = false  //是否为克隆节点
    this.isOnce = false    //是否为v-once节点
    this.asyncFactory = asyncFactory // 异步工厂方法
    this.asyncMeta = undefined //异步Meta
    this.isAsyncPlaceholder = false //是否为异步占位
  }
  //容器实例向后兼容的别名
  get child (): Component | void {
    return this.componentInstance
  }
}

实现比较简单,我就不过多赘述了,这里顺带介绍三个VNode类型

文本节点,只有text属性


{
    text : "hello world"
}

注释节点,只有text属性和isComment属性


{
    text : "hello world",
    isComment : true
}

元素节点,只有tag(标签名),data(节点数据),children(子节点列表),context(当前组件的vue.js实例)


{
    tag : "div",
    data : {...},
    children : [{...},{...}],
    context : {...}
}

这三种之外还有克隆节点,组件节点,函数式组件节点,不过本文讨论的重点不在这,所以暂且省略。

patch和patchVNode

将虚拟DOM渲染成真实DOM的操作是patch。patch中的核心是diff算法,diff算法做的一个很重要的优化就是,只比较同层次的节点,这使diff的时间复杂度降到了O(n)

patch在_update方法中被调用,代码如下


Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
    const vm: Component = this
    if (vm._isMounted) {
      callHook(vm, 'beforeUpdate')
    }
    const prevEl = vm.$el
    const prevVnode = vm._vnode
    const prevActiveInstance = activeInstance
    activeInstance = vm
    vm._vnode = vnode
    if (!prevVnode) {
      // initial render
      vm.$el = vm.__patch__(
        vm.$el, vnode, hydrating, false /* removeOnly */,
        vm.$options._parentElm,
        vm.$options._refElm
      )
    } else {
      // updates
      // 更新视图
      vm.$el = vm.__patch__(prevVnode, vnode)
    }
    activeInstance = prevActiveInstance
    // update __vue__ reference
    if (prevEl) {
      prevEl.__vue__ = null
    }
    if (vm.$el) {
      vm.$el.__vue__ = vm
    }
    // if parent is an HOC, update its $el as well
    if (vm.$vnode && vm.$parent && vm.$vnode === vm.$parent._vnode) {
      vm.$parent.$el = vm.$el
    }
    // updated hook is called by the scheduler to ensure that children are
    // updated in a parent's updated hook.
  }

我们可以看到,vm_patch执行时传入了两个参数,前一个参数代表旧的VNode,第二个参数代表新的VNode,比较旧VNode和新VNode的差异,和把VNode渲染成真实DOM,就是在patch中完成的。而patch函数的返回值,重新赋值到vm.$el上,由此可见,patch函数一般会传入vue挂载的根结点对应的Vdom。

来看看patch的算法




function patch(oldVnode, vnode, hydrating, removeOnly) {
        // 如果新vnode不存在,直接调用销毁钩子
        if (isUndef(vnode)) {
            if (isDef(oldVnode)) invokeDestroyHook(oldVnode)
            return
        }

        let isInitialPatch = false
        const insertedVnodeQueue = []
        // 如果旧Vnode不存在,直接创建新的节点
        // empty mount (likely as component), create new root element
        if (isUndef(oldVnode)) {
            isInitialPatch = true
            createElm(vnode, insertedVnodeQueue)
        } else {
            // nodeType只有元素节点才有,注释和文本节点都无
            // 可以通过判断nodeType判断是不是元素节点
            const isRealElement = isDef(oldVnode.nodeType)
            if (!isRealElement && sameVnode(oldVnode, vnode)) {
                // 如果新旧节点是同一个,调用patchVnode继续对比
                patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
            } else {
                if (isRealElement) {
                    // mounting to a real element
                    // check if this is server-rendered content and if we can perform
                    // a successful hydration.
                    if (oldVnode.nodeType === 1 && oldVnode.hasAttribute(SSR_ATTR)) {
                        oldVnode.removeAttribute(SSR_ATTR)
                        hydrating = true
                    }
                     // 当旧的VNode是服务端渲染的元素,合并旧VNode到真实DOM上
                     // 合并成功调用相应钩子,失败就报不一致警告
                    if (isTrue(hydrating)) {
                        if (hydrate(oldVnode, vnode, insertedVnodeQueue)) {
                            invokeInsertHook(vnode, insertedVnodeQueue, true)
                            return oldVnode
                        } else if (process.env.NODE_ENV !== 'production') {
                            warn(
                                'The client-side rendered virtual DOM tree is not matching ' +
                                'server-rendered content. This is likely caused by incorrect ' +
                                'HTML markup, for example nesting block-level elements inside ' +
                                '<p>, or missing <tbody>. Bailing hydration and performing ' +
                                'full client-side render.'
                            )
                        }
                    }
                    // either not server-rendered, or hydration failed.
                    // create an empty node and replace it
                    // 如果不是服务端渲染或者合并到真实DOM失败,则创建一个空的VNode节点替换它
                    oldVnode = emptyNodeAt(oldVnode)
                }

                // replacing existing element
                // 替换现有的元素
                const oldElm = oldVnode.elm
                const parentElm = 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,
                    nodeOps.nextSibling(oldElm)
                )

                // update parent placeholder node element, recursively
                if (isDef(vnode.parent)) {
                    let ancestor = vnode.parent
                    const patchable = isPatchable(vnode)
                    while (ancestor) {
                        for (let i = 0; i < cbs.destroy.length; ++i) {
                            cbs.destroy[i](ancestor)
                        }
                        ancestor.elm = vnode.elm
                        if (patchable) {
                            for (let i = 0; i < cbs.create.length; ++i) {
                                cbs.create[i](emptyNode, ancestor)
                            }
                            // #6513
                            // invoke insert hooks that may have been merged by create hooks.
                            // e.g. for directives that uses the "inserted" hook.
                            const insert = ancestor.data.hook.insert
                            if (insert.merged) {
                                // start at index 1 to avoid re-invoking component mounted hook
                                for (let i = 1; i < insert.fns.length; i++) {
                                    insert.fns[i]()
                                }
                            }
                        } else {
                            registerRef(ancestor)
                        }
                        ancestor = ancestor.parent
                    }
                }

                // destroy old node
                // 销毁旧节点
                if (isDef(parentElm)) {
                    removeVnodes([oldVnode], 0, 0)
                } else if (isDef(oldVnode.tag)) {
                    invokeDestroyHook(oldVnode)
                }
            }
        }

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


从代码中可以看出,patch比较新旧VNode时,会先判断新旧VNode是否为同一个节点,如果是同一个节点,调用patchVnode方法来继续比较,否则,直接删除旧节点,直接重新渲染一个新节点。

那么怎么样算同一个节点呢,我们来看看sameVNode的实现,可以看出来sameVNode返回true时,两个节点不一定相同


  // 能判定为sameVnode必须满足下面的条件
  // key相同
  // tag相同(当前节点的标签名相同)
  // isComment相同(是否为注释节点相同)
  // data是否均为undefined或者均不为undefined
  // InputType必须相同
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)
  )
}
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
}

然后我们看看 patchVnode 的实现


function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    // 如果传入的新旧VNode节点相同则直接返回
    if (oldVnode === vnode) {
      return
    }
    // 如果新旧节点均为静态节点,并且新旧节点的key相同,并且新节点是克隆节点或者只渲染一次的节点,可以直接把旧节点的ele或者componentInstance复制到新节点上,这样就不用再次把VNode转化成真实DOM了
    if (isTrue(vnode.isStatic) &&
        isTrue(oldVnode.isStatic) &&
        vnode.key === oldVnode.key &&
        (isTrue(vnode.isCloned) || isTrue(vnode.isOnce))) {
      vnode.elm = oldVnode.elm
      vnode.componentInstance = oldVnode.componentInstance
      return
    }
    let i
    const data = vnode.data
    if (isDef(data) && isDef(i = data.hook) && isDef(i = i.prepatch)) {
      i(oldVnode, vnode)
    }
    const elm = vnode.elm = oldVnode.elm
    const oldCh = oldVnode.children
    const ch = vnode.children
    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)
    }
    // 如果这个VNode节点没有text属性
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        // 新老节点都有子节点,对子节点继续进行diff比较
        if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
      } else if (isDef(ch)) {
        // 如果老节点没有子节点而新节点存在子节点,先清空真实DOM的文本内容,然后为当前节点加入子节点
        if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
        addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
      } else if (isDef(oldCh)) {
        // 当新节点没有子节点而老节点有子节点的时候,则移除真实DOM的子节点
        removeVnodes(elm, oldCh, 0, oldCh.length - 1)
      } else if (isDef(oldVnode.text)) {
        // 当新老节点都无子节点的时候,只是文本的替换,因为这个逻辑中新节点text不存在,所以直接去除真实DOM的文本
        nodeOps.setTextContent(elm, '')
      }
    } else if (oldVnode.text !== vnode.text) {
      // 当新老节点text不一样时,直接替换这段文本
      nodeOps.setTextContent(elm, vnode.text)
    }
    // 调用postpatch钩子
    if (isDef(data)) {
      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. 当新老节点都无子节点的时候,只是文本的替换。

你可能会疑惑patch和patchNode和updateChildren的区别,我们来看看他们调用的时机和实际的效果,patch中的patchNode是在确定新旧节点是同一个节点的情况下调用的


if (!isRealElement && sameVnode(oldVnode, vnode)) {
    // 如果新旧节点是同一个,调用patchVNode方法
    patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
} 

patchVnode的用处有两个

  1. 把两个判定为sameVnode的节点进行进一步的比较和替换
  2. 调用 updateChildren 比较子节点

所以patchVNode仍然是在比较patch中的节点,只有 updateChildren 才是真正开始比较子节点。但是我一直搞不懂的是,如果sameVnode判定是true的话,两个节点应该基本属于一个相同的VNode类型,文字节点不可能有children属性,元素节点也不可能有text属性,所以3的情况,应该进不到patchVNode里.....事实上我调试了半天也没调试出这种情况.....暂且略过8,有空再回头看看

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, elmToMove, refElm
    // removeOnly is a special flag used only by 
    // to ensure removed elements stay in correct relative positions
    // during leaving transitions
    const canMove = !removeOnly
    // 循环遍历子节点数组
    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] : null
        if (isUndef(idxInOld)) { // New element
          createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
          newStartVnode = newCh[++newStartIdx]
        } else {
          elmToMove = oldCh[idxInOld]
          /* istanbul ignore if */
          if (process.env.NODE_ENV !== 'production' && !elmToMove) {
            warn(
              'It seems there are duplicate keys that is causing an update error. ' +
              'Make sure each v-for item has a unique key.'
            )
          }
          if (sameVnode(elmToMove, newStartVnode)) {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
            oldCh[idxInOld] = undefined
            canMove && nodeOps.insertBefore(parentElm, newStartVnode.elm, oldStartVnode.elm)
            newStartVnode = newCh[++newStartIdx]
          } else {
            // same key but different element. treat as new element
            createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm)
            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)
    }
  }

变量指向如图

updateChildren对比子节点的方式是从中间到两边对比,也就是两边向中间处理节点,图中index和指向的变量映射如下。

  1. oldStartIdx指向的节点是 oldStartVnode,旧VNode中未处理的第一个节点
  2. oldEndIdx指向的节点是oldEndVnode, 旧VNode中未处理的最后一个节点
  3. newStartIdx指向的节点是newStartVnode, 新VNode中未处理的第一个节点
  4. newEndIdx指向的节点是newEndVnode, 新VNode中未处理的最后一个节点

遍历中,如果存在key,并且满足sameVnode,会将该DOM节点进行复用,否则则会创建一个新的DOM节点。

在大多数情况下,节点的变化情况不大,可以进行预测,每次循环中先使用这四种情况进行比对,就可以处理大部分的情况。

  1. oldStartVnode和newStartVnode对比
  2. oldEndVnode和newEndVnode 对比
  3. oldStartVnode和newEndVnode 对比
  4. oldEndVnode和newStartVnode 对比

如果调用sameVNode对比的结果是true,调用patchVnode方法继续比较,不过如果是3, 4为true的情况,那就证明新VNode中节点的位置发生了改变,还需要移动真实DOM,其中情况3会把 oldStartVnode 对应的真实DOM移动到所有未处理节点的后面,情况4会把 oldEndVnode 对应的真实DOM移动到所有未处理节点的前面。

如果以上情况均不符合,且 如果oldVNode数组中的节点有key属性(通过v-key设置),则通过createKeyToOldIdx会得到一个名为oldKeyToIdx的对象,这个对象的键是oldVNode的key属性,值是oldVNode在节点数组中的下标。从这个对象上可以直接找到是否有与newStartVnode一致key的旧的VNode节点, 如果两两个key相同的VNode满足sameVnode,patchVnode的同时会将这个真实DOM(elmToMove)移动到oldStartVnode对应的真实DOM的前面。

但如果没有设置key属性,虽然也会调用 createKeyToOldIdx会得到一个名为oldKeyToIdx的对象 ,但是这个对象上没有属性,所以不能作为map使用,vue就会使用就地替换策略,直接创建新的真实DOM用于替换。还有找不到一致key或者key相同但 sameVnode 不满足的时候,也会直接创建真实DOM,这就是为什么建议在v-for中使用v-key的原因,因为通过key生成对象,可以减少查找时间,并且可以对真实DOM进行移动操作,而不是创建新的节点用于就地替换。

来看看循环结束时的情况,因为循环能继续的条件是oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx,那么只要新旧节点数量不一致就会出现出现一边startIndex和oldIndex没有碰头的情况,这时候我们要去处理真实DOM中多余的节点或者添加真实DOM中不够的节点。

当结束时oldStartIdx > oldEndIdx,这说明了新的VNode节点比老的VNode节点多,也就是比真实DOM多,需要将剩下的(也就是新增的)VNode节点插入到真实DOM节点中去,此时通过调用addVnodes(批量调用createElm的接口)将这些节点加入到真实DOM中去。

当结束时newStartIdx > newEndIdx时, 新的VNode节点比老的VNode节点少,也就是比真实DOM多少, 需要将剩下的(也就是多余的)VNode节点删除,通过调用removeVnodes(批量调用浏览器api中的element.removeChild)将这些多余的真实DOM删除。

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00