Vue中的虚拟DOM及diff算法

摘要：的算法是基于的实现，并在些基础上作了很多的调整和改进。此时和之间的是新增的，调用，把这些虚拟全部插进的后边，可以认为新节点先遍历完。

为什么出现：

浏览器解析一个html大致分为五步：创建DOM tree –> 创建Style Rules -> 构建Render tree -> 布局Layout –> 绘制Painting。每次对真实dom进行操作的时候，浏览器都会从构建dom树开始从头到尾执行一遍流程。真实的dom操作代价昂贵，操作频繁还会引起页面卡顿影响用户体验，虚拟dom就是为了解决这个浏览器性能问题才被创造出来

虚拟dom在执行dom的更新操作后，虚拟dom不会直接操作真实dom，而是将更新的diff内容保存到本地js对象中，然后一次性attach到dom树上，通知浏览器进行dom绘制避免大量无谓的计算。

如何实现：

js对象表示dom结构，对象记录了dom节点的标签、属性和子节点

js对象的render函数通过对虚拟dom的属性和子节点的递归构建出真实dom树

虚拟DOM是一个纯粹的JS对象，可以通过document.createDocumentFragment 创建，Vue中一个虚拟DOM包含以下属性：

tag: 当前节点的标签名
data: 当前节点的数据对象
children: 数组类型，包含了当前节点的子节点
text: 当前节点的文本，一般文本节点或注释节点会有该属性
elm: 当前虚拟节点对应的真实的dom节点
context: 编译作用域
functionalContext: 函数化组件的作用域
key: 节点的key属性，用于作为节点的标识，有利于patch的优化
sel: 节点的选择器
componentOptions: 创建组件实例时会用到的选项信息
child: 当前节点对应的组件实例
parent: 组件的占位节点
raw: raw html
isStatic: 静态节点的标识
isRootInsert: 是否作为根节点插入，被包裹的节点，该属性的值为false
isComment: 当前节点是否是注释节点
isCloned: 当前节点是否为克隆节点
isOnce: 当前节点是否有v-once指令

简单总结：虚拟DOM是将真实的DOM节点用JavaScript模拟出来，将DOM变化的对比，放到 Js 层来做。

优势：

跨平台：Virtual DOM 是以 JavaScript 对象为基础而不依赖真实平台环境，所以使它具有了跨平台的能力，比如说浏览器平台、Weex、Node 等。

提高DOM操作效率：DOM操作的执行速度远不如Javascript的运算速度快，因此，把大量的DOM操作搬运到Javascript中，运用patching算法来计算出真正需要更新的节点，最大限度地减少DOM操作，从而显著提高性能。

提升渲染性能：在大量、频繁的数据更新下，依托diff算法，能够对视图进行合理、高效的更新。

Vue.js通过编译将template 模板转换成渲染函数(render ) ，执行渲染函数就可以得到一个虚拟节点树

在对 Model 进行操作的时候，会触发对应 Dep 中的 Watcher 对象。Watcher 对象会调用对应的 update 来修改视图。这个过程主要是将新旧虚拟节点进行差异对比（patch），然后根据对比结果进行DOM操作来更新视图。

diff算法是一种优化手段，将前后两个模块进行差异对比，修补(更新)差异的过程叫做patch
patch：
虚拟DOM最核心的部分，它可以将vnode渲染成真实的DOM，这个过程是对比新旧虚拟节点之间有哪些不同，然后根据对比结果找出需要更新的的节点进行更新。
patch本身就有补丁、修补的意思，其实际作用是在现有DOM上进行修改来实现更新视图的目的。Vue的Virtual DOM patching算法是基于Snabbdom的实现，并在些基础上作了很多的调整和改进。

当数据发生改变时，set方法会让调用Dep.notify通知所有订阅者Watcher，订阅者就会调用patch给真实的DOM打补丁，更新相应的视图。

Vue的diff算法是仅在同级的vnode间做diff，递归地进行同级vnode的diff，最终实现整个DOM树的更新。因为跨层级的操作是非常少的，忽略不计，这样时间复杂度就从O(n3)变成O(n)。

diff算法的假设

Web UI 中 DOM 节点跨层级的移动操作特别少，可以忽略不计。

拥有相同类的两个组件将会生成相似的树形结构，拥有不同类的两个组件将会生成不同的树形结构。

对于同一层级的一组子节点，它们可以通过唯一 id 进行区分。

当新旧虚拟节点的key和sel都相同时，则进行节点的深度patch，若不相同则整个替换虚拟节点，同时创建真实DOM，实现视图更新。

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

function patch (oldVnode, vnode) {
    if (sameVnode(oldVnode, vnode)) { // 有必要进行patch, key和sel都相同时才进行patch
        patchVnode(oldVnode, vnode)
    } else {  // 没有必要进行patch, 整个替换
        const oEl = oldVnode.el
        let parentEle = api.parentNode(oEl)
        createEle(vnode) // vnode创建它的真实dom，令vnode.el =真实dom
        if (parentEle !== null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl)) // 插入整个新节点树
            api.removeChild(parentEle, oldVnode.el) // 移出整个旧的虚拟DOM
            oldVnode = null
        }
    }
    return vnode
}

深度patch：

 function patchVnode (oldVnode, vnode, insertedVnodeQueue, removeOnly) {
    /*两个VNode节点相同则直接返回*/
    if (oldVnode === vnode) {
      return
    }
    // reuse element for static trees.
    // note we only do this if the vnode is cloned -
    // if the new node is not cloned it means the render functions have been
    // reset by the hot-reload-api and we need to do a proper re-render.
    /*
      如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），
      并且新的VNode是clone或者是标记了once（标记v-once属性，只渲染一次），
      那么只需要替换elm以及componentInstance即可。
    */
    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 = data.hook.prepatch，如果存在的话，见"./create-component componentVNodeHooks"。*/
      i(oldVnode, vnode)
    }
    const elm = vnode.elm = oldVnode.elm
    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文本时*/
    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)
    }
    /*调用postpatch钩子*/
    if (isDef(data)) {
      if (isDef(i = data.hook) && isDef(i = i.postpatch)) i(oldVnode, vnode)
    }
  }

patchVnode的规则

1.如果新旧VNode都是静态的，同时它们的key相同（代表同一节点），那么只需要替换elm以及componentInstance即可（原地复用）。

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

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

4.如果只有老节点有子节点，直接删除老节点的子节点。

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

接下来就是最复杂的diff算法的理解

updateChildren (parentElm, oldCh, newCh) {
    let oldStartIdx = 0, 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
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        if (oldStartVnode == null) {   // 对于vnode.key的比较，会把oldVnode = null
            oldStartVnode = oldCh[++oldStartIdx] 
        }else if (oldEndVnode == null) {
            oldEndVnode = oldCh[--oldEndIdx]
        }else if (newStartVnode == null) {
            newStartVnode = newCh[++newStartIdx]
        }else if (newEndVnode == null) {
            newEndVnode = newCh[--newEndIdx]
        }else if (sameVnode(oldStartVnode, newStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode)
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
        }else if (sameVnode(oldEndVnode, newEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode)
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
        }else if (sameVnode(oldStartVnode, newEndVnode)) {
            patchVnode(oldStartVnode, newEndVnode)
            api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
        }else if (sameVnode(oldEndVnode, newStartVnode)) {
            patchVnode(oldEndVnode, newStartVnode)
            api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
        }else {
           // 使用key时的比较
            if (oldKeyToIdx === undefined) {
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表
            }
            idxInOld = oldKeyToIdx[newStartVnode.key]
            if (!idxInOld) {
                api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                newStartVnode = newCh[++newStartIdx]
            }
            else {
                elmToMove = oldCh[idxInOld]
                if (elmToMove.sel !== newStartVnode.sel) {
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                }else {
                    patchVnode(elmToMove, newStartVnode)
                    oldCh[idxInOld] = null
                    api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                }
                newStartVnode = newCh[++newStartIdx]
            }
        }
    }
    if (oldStartIdx > oldEndIdx) {
        before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
    }else if (newStartIdx > newEndIdx) {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
}

将Vnode的子节点Vch和oldVnode的子节点oldCh提取出来

oldCh和vCh各有两个头尾的变量StartIdx和EndIdx，它们的2个变量相互比较，一共有4种比较方式，，当其中两个能匹配上那么真实dom中的相应节点会移到Vnode相应的位置。如果4种比较都没匹配，如果设置了key，就会用key进行比较，在比较的过程中，变量会往中间靠，一旦StartIdx>EndIdx表明oldCh和vCh至少有一个已经遍历完了，就会结束比较。

在新老两个VNode节点的左右头尾两侧都有一个变量标记，在遍历过程中这几个变量都会向中间靠拢。当oldStartIdx <= oldEndIdx或者newStartIdx <= newEndIdx时结束循环。

我们通过一个例子来理解整个对比过程：

真实节点：a，b，d

旧节点：a，b，d

新节点：a，c，d，b

第一步：

oldS = a, oldE = d；
S = a, E = b;

oldS和S，E比较；oldE和S，E比较，得出oldS和S匹配的结论，于是a节点应该按照新节点的顺序放置在第一个。此时旧节点的a节点也在第一个，故而位置不动；

第一轮对比结束oldS和S为同一节点，向后移动，oldE和E不动；

第二步：

旧节点：a，b，d

新节点：a，c，d，b

oldS = b, oldE = d；
S = c, E = b;

四个变量两辆对比可得oldS和E匹配，将原本的b节点移动到最后，因为E是最后一个节点，他们位置要一致，这就是上面说的：当其中两个能匹配上那么真实dom中的相应节点会移到Vnode相应的位置；

第二轮对比结束，oldE和E为同一节点，向前移动，oldS和S位置不动；

第三步：

旧节点：a，d，b

新节点：a，c，d，b

oldS = d, oldE = d；
S = c, E = d;

oldE和E匹配，位置不变;

第四步：

旧节点：a，d，b

新节点：a，c，d，b

oldS++;
oldE--;
oldS > oldE;

遍历结束，说明旧节点先遍历完。就将剩余的新节点c根据自己的的index插入到真实dom中去

旧节点：a，c，d，b

新节点：a，c，d，b

对比完成。

当然也会存在四个变量无法互相匹配，分为两种情况

如果新旧子节点都存在key，那么会根据旧节点的key生成一张hash表，用S的key与hash表做匹配，匹配成功就判断S和匹配节点是否为sameNode，如果是，就在真实dom中将成功的节点移到最前面，否则，将S生成对应的节点插入到dom中对应的oldS位置，oldS和S指针向中间移动。

如果没有key,则直接将S生成新的节点插入真实DOM （这里可以解释为什么设置key会让diff更高效

结束时存在两种具体的情况：

oldS > oldE，可以认为旧节点先遍历完。当然也有可能新节点此时也正好完成了遍历，统一都归为此类。此时S和E之间的vnode是新增的，调用addVnodes，把这些虚拟node.elm全部插进before的后边.

S> E，可以认为新节点先遍历完。此时oldS和oldE之间的节点在新的子节点里已经不存在了，直接删除

在模拟两个例子体会一下

eg.1
O b,a,d,f,e
N a,b,e
1. 
oldS = b, oldE = e；
S = a, E = e;
O b,a,d,f,e
N a,b,e
2.
oldS = b, oldE = f；
S = a, E = b;
O a,d,f,b,e
N a,b,e
3.
s>e d,f 删除
O a,b,e
N a,b,e

eg.2
O b,d,c,a
N a,e,b,f
1. 
oldS = b, oldE = a；
S = a, E = f;
O a,b,d,c
N a,e,b,f
2.
oldS = d, oldE = c；
S = e, E = f;
此时四个参数无法匹配，根据key来对比O中是否有S对应的节点，没有，则在O的S位置插入对应节点
O a,e,d,b,c
N a,e,b,f
3.
oldS = d, oldE = c；
S = b, E = f;
此时四个参数无法匹配,根据key查找是否有S对应的B节点，有，移动到S当前的位置
O a,e,b,d,c
N a,e,b,f
4.
oldS = d, oldE = c；
S = f, E = f;
此时四个参数无法匹配,根据key查找是否有S对应的f节点,没有，则在O的S位置插入对应节点
O a,e,b,d,c,f
N a,e,b,f
5.
oldS = d, oldE = c；
s>f
循环结束，oldS与oldE之间的节点删除

总结：

尽量不要跨层级的修改dom

在开发组件时，保持稳定的 DOM 结构会有助于性能的提升

设置key可以让diff更高效

参考：

详解Vue中的虚拟DOM

VirtualDOM与diff(Vue实现)

虚拟DOM介绍

数据更新到视图更新，Vue做了什么

详解vue的diff算法