什么是虚拟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的语法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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属性

1
2
3
{
    text : "hello world"
}

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

1
2
3
4
{
    text : "hello world",
    isComment : true
}

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

1
2
3
4
5
6
{
    tag ： "div"，
    data : {...},
    children : [{...},{...}],
    context : {...}
}

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

patch和patchVNode

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

patch在update方法中被调用，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

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时，两个节点不一定相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  // 能判定为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 的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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是在确定新旧节点是同一个节点的情况下调用的

1
2
3
4
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

先上源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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删除。