虚拟DOM和diff算法的原理和实现

一、什么是虚拟DOM

虚拟DOM就是将真实DOM映射成一个数据对象，这个数据对象将以以下形式展现：

1
2
3
4
5
6
7
8
9
10
11
12
13
// vnode.js
export default function vnode(sel, data, children, text, elm) {
    const key = data?.key

    return {
        sel, // 保存DOM的标签名，如果该DOM是一个DIV元素，那么这里的值就是div
        data,   // 保存DOM的class、props、style等属性，其中最主要的就是key属性，它会用于后续diff排序的工作
        children,  // 保存DOM的子节点，当该属性为空的时候，说明这个DOM节点是一个文本节点
        text,   // 保存DOM的文本内容
        elm, // 保存真实DOM，最终操作真实DOM会通过这个属性来操作。
        key    // 将data中的key属性外置的一个属性，方便外部直接访问
    }
}

二、为什么需要虚拟DOM

在现实开发中，如果频繁去操作真实DOM，其开销是巨大的。
比如说反复修改一百次一个DOM节点的文本内容，如果每次都去操作真实DOM，那就会造成不必要的性能开销。因为其实真正应用到真实DOM的文本内容只有最后一次。
这个时候如果使用虚拟DOM来接收这些操作，那其实就只是将VNode对象中的text属性修改一百次，这样的性能开销基本可以小到忽略不计。
最后将虚拟DOM的最终结果应用到真实DOM上面去，这远比操作一百次真实DOM来的更有效率一些。
当然，这是比较极端的情况，像Chrome这类浏览器本身也有对这种一次性反复修改DOM的操作进行了优化。
而实际使用中，虚拟DOM更多时候是配合diff算法来优化性能的，以应对更复杂的DOM操作场景。

三、如何实现一个虚拟DOM

在第一节已经实现了一个虚拟DOM对象的数据结构，现在需要返回一个子节点也是虚拟DOM的对象，那么就需要做进一步处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// h.js
import VNode from './vnode.js'
export default function h(tag, data, params) {
    if (typeof params == 'string') {    // 如果params是一个文本类型的数据，那么说明该节点是一个文本节点。
        return new vnode(tag, data, undefined, params, undefined)
    }
    else if (Array.isArray(params)) {   // 如果params是一个数组，那么说明该节点有子节点
        let children = []
        for (let item of params) {
            children.push(item)
        }
        return new vnode(tag, data, children, undefined, undefined)
    }
}

四、什么是diff算法

接着说说diff算法，diff算法是一种对比算法，它能够高效率的比较出新旧两颗虚拟DOM树之间的差异，最后将差异的部分应用到真实DOM上面去 。
目前最主流的diff算法是snabbdom算法，像Vue用的就是改进版的snabbdom算法。

五、diff算法的实现思路

如果对两颗DOM树进行完全比较，那么时间复杂度起码会是O(n^3)，当DOM树非常大的时候，这样的比较会非常消耗性能。
而现实开发中，很少出现跨层级调整节点的情况，所以diff算法就规定只在同层级之间比较。跨层级之间的调整直接暴力删除然后重新创建。
这样下来，时间复杂度就降低到了O（n）。

flowchart LR
    direction LR
    subgraph OLD_VDOM
        direction TB
        ul1(ul) ---> li1(li) & li2(li)
        subgraph LI1
            li1
            li2
        end
        li1 ---> p1(p) & p2(p)
        li2 ---> p3(p) & p4(p)
        subgraph P1
            p1
            p2
            p3
            p4
        end
    end
    subgraph NEW_VDOM
        direction TB
        ul2(ul) ---> li3(li) & li4(li)
        subgraph LI2
            li3
            li4
        end
        li3 ---> p5(p) & p6(p)
        li4 ---> p7(p) & p8(p)
        subgraph P2
            p5
            p6
            p7
            p8
        end
    end
    ul1 -.->|对比| ul2
    LI1 -.->|对比| LI2
    P1 -.->|对比| P2

接着，在对比的时候，算法会优先去比较每个节点的子节点，然后再去比较同层级的相邻节点，所以diff算法是一种深度优先的算法。

在比较的时候，算法首先会先比较节点的sel属性。如果节点之间sel属性不同，那么就直接暴力删除，然后创建一个新的节点。
如果sel属性相同，那就判断新旧VDOM有没有子节点，这里分为三种情况：

  • 新VDOM没有子节点
    说明新的VDOM是一个文本节点，那么就直接清空旧VDOM的innerHTML，再将text赋值给旧VDOM的innerText属性
  • 新VDOM有子节点，旧VDOM没有子节点
    那就清空旧VDOM的innerText，然后递归新VDOM的children创建Elemenet。
  • 新VDOM有子节点，旧VDOM也有子节点
    在这个情况便是diff算法要解决的核心问题，我们需要通过sel和key属性来对比每个子节点之间是否相同，然后决定是要创建、删除或重新调整顺序。
    这种场景我们很自然地会想到使用双层嵌套的for循环来进行逐个节点的对比，这样做的时间复杂度将会是O(n^2)，很显然不够高效。
    而snabbdom算法给出的解决方案是使用首尾指针法+map映射表，可以将时间复杂度降低到O（n）。
    具体做法就是：
    先给新旧DOM树都定义一对Start和End指针，分别指向子元素数组的第一个跟最后一个，然后按以下四种情况逐个拿出来跟另一颗DOM树对应的节点进行对比：
    • 旧DOM树的Start节点跟新DOM树的Start节点进行对比。如果相同，指针都向前挪一位，进行下一对节点的对比。如果不同，就进入下一种情况
    • 旧DOM树的End节点跟新DOM树的End节点进行对比。相同，指针向后挪一位，不同，进入下一种情况
    • 旧DOM树的Start节点跟新DOM树的End节点对比。相同，调整旧DOM树的节点位置，旧DOM树Start指针往前，新DOM树End指针往后。不同，进入下一种情况。
    • 旧DOM树的End节点跟新DOM树的Start节点对比。相同，调整旧DOM树的节点位置，旧DOM树End指针往后，新DOM树Start指针往前。不同，就脱离了首尾指针算法的运算范畴，进入第五种情况，使用map映射表算法来查询节点。
    • 取出旧DOM树每个节点的key属性和它的index序号，做成一个键值对映射表，接着拿新DOM树节点的key属性去查询这个映射表，如果查到了，就根据index序号调整节点位置，查不到就当场创建这个节点，并插入到旧DOM树Start节点的下面。
    • 当以上循环跑完之后，如果出现旧DOM树的Start指针大于End指针，那就说明新DOM树有新增的节点，需要将新增的节点插入到新DOM树End指针指向的节点下面
    • 如果是新DOM树的Start指针对于End指针，则说明新DOM树有删除掉的节点，这时只需要将旧DOM树Start指针到End指针之间的节点全部删除即可
      到这里就完成了对diff算法的核心思路构想，接下来就是把它实现到代码中。

六、diff算法的具体实现

在snabbdom算法中，首先会有个patch函数将新虚拟DOM的改动应用到旧虚拟DOM之中，具体实现如下：

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
// patch.js
import vnode from './vnode'
import createElm from './createElm'
import patchVNode from './patchVNode'
export default function patch(oldNode, newNode) {
    if (oldNode.sel === undefined) { // 如果没有sel属性，说明传入的oldNode是最初将要被挂载的根节点，只需要将它转化成一个空的虚拟DOM节点即可
        oldNode = vnode(
            oldNode.tagName.toLowerCase(),
            {}
            [],
            undefined,
            oldNode
        )
    }

    // 接着是比较新旧节点的sel属性
    if (oldNode.sel === newNode.sel) {
        // 相同则通过patchVNode函数比较其内容
        patchVNode(oldNode, newNode)
    }
    else {
        // 不同则暴力删除并创建
        let newVNodeElm = createElm(newNode.elm)
        let oldVNodeElm = oldNode.elm

        if (newVNodeElm) {
            oldVNodeElm.parentNode.insertBefore(newVNodeElm, oldVNodeElm)
            oldVNodeElm.parentNode.removeChild(oldVNodeElm)
        }
    }
}

这里涉及两个新的函数createElm和patchVNode。

createElm实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// createElm.js
export default function createElm(vnode) {
    let domNode = document.createElement(vnode.sel)

    // 如果vnode的children属性为空，说明当前节点是文本节点
    if(vnode.children === undefined) {
        domNode.innerText = vnode.text
    }
    // 如果vnode的children属性不为空，则递归创建children
    else if (Array.isArray(vnode.children)) {
        for (let c of vnode.children) {
            let cNode = createElm(c.sel)
            domNode.appendChild(cNode)
        }
    }

    vnode.elm = domNode
    return domNode
}

而patchVNode的具体实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// patchVNode.js
import updateChildren from 'updateChildren'
export default function patchVNode(oNode, nNode) {
    // 如果新节点没有子节点，说明新节点是个文本节点，直接将新节点的文本内容覆盖到旧节点上面去即可
    if (nNode.children === undefined) {
        if (oNode.text !== nNode.text) oNode.elm.innerText = nNode.text
        return
    }
    
    // 如果旧节点没有子节点，直接创建新节点的子节点并添加到旧节点上面去
    if (oNode.children !== undefined || oNode.children.length <= 0) {
        oNode.elm.innerHtml = ''
        for (let c of nNode.children) {
            let cDom = createElm(nNode.children)
            oNode.elm.appendChild(nDom)
        }
        return
    }

    // 如果旧节点也有子节点，那就是最复杂的情况，需要通过diff的核心算法来调整其子节点
    updateChildren(oNode.elm, oNode.children, nNode.children)
}

接下来就是diff算法最核心函数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
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
// updateChildren.js
import patchVnode from 'patchVnode'
import sameNode from 'sameNode'

function sameNode(oNode, nNode) {
    return oNode?.key === nNode?.key
}

export default function updateChildren(parentElm, oldCh, newCh) {
    // 定义新旧节点的首尾指针
    let oStartIdx = 0
    let oEndIdx = oldCh.length - 1
    let nStartIdx = 0
    let nEndIdx = newCh.length - 1

    // 定义新旧节点首尾指针指向的Node
    let oStartNode = oldCh[oStartIdx]
    let oEndNode = oldCh[oEndIdx]
    let nStartNode = newCh[nStartIdx]
    let nEndNode = newCh[nEndIdx]

    while (oStartIdx <= oEndIdx && nStartIdx <= nEndIdx) {

        // key map算法中会将节点置为空，所以遇到的时候直接跳过
        if (oStartNode === undefined) {
            oStartNode = oldCh[++oStartIdx]
            continue
        }
        
        if (oEndNode === undefined) {
            oEndNode = newCh[--oEndIdx]
            continue
        }

        // 对比两个Start节点，如果相同直接替换内容
        if (sameNode(oStartNode, nStartNode)) {
            patchVNode(oStartNode, nStartNode)
            // 指针向前进一位
            oStartNode = oldCh[++oStartIdx]
            nStartNode = newCh[++nStartIdx]
        }
        // 对比两个End节点
        else if (sameNode(oEndNode, nEndNode)) {
            patchVNode(oEndNode, nEndNode)
            // 指针往后退一位
            oEndNode = oldCh[--oEndIdx]
            nEndNode = newCh[--nEndIdx]
        } 
        // 对比旧Start节点和新End节点
        else if (sameNode(oStartNode, nEndNode)) {
            patchVNode(oStartNode, nEndNode)
            // 调整顺序将旧Start节点挪到旧End节点后面
            patentElm.insertBefore(oStartNode.elm, nEndNode.elm.nextSibling)

            // Start的往前，End的往后
            oStartNode = oldCh[++oStartIdx]
            nEndNode = newCh[--nEndIdx]
        }
        // 对比旧End节点和新Start节点
        else if (sameNode(oEndNode, nStartNode)) {
            patchVNode(oEndNode, nStartNode)
            parentElm.insertBefore(oEndNode.elm, oStartNode.elm)

            oEndNode = oldCh[--oEndIdx]
            nStartNode = newCh[++nStartIdx]
        }
        // 如果以上四种情况都不匹配，就生成key map直接查找
        else {
            let keys = {}

            // 通过旧节点的children生成key map
            for (let i = 0; i < oldCh.length; i ++) {
                let n = oldCh[i]
                if (n.key) keys[n.key] = i
            }

            // 查找key map中有没有新节点的key
            let idxInOld = keyMap[nStartNode.key]

            // 如果有就修改内容并调整位置
            if (idxInOld) {
                const elm2Move = oldCh[idxInOld]
                patchVNode(elm2Move, nStartNode)
                parentElm.insertBefore(elm2Move, oStartNode.elm)
                // 将旧节点的对应子元素置为空，指针碰到的时候直接跳过
                oldCh[idxInOld] = undefined
            }
            // 没有就直接创建
            else {
                parentElm.insertBefore(createElm(nStartNode), oStartNode.elm)
            }

            nStartNode = newCh[++nStartIdx]
        }
    }

    // 当跳出循环时，如果旧节点的Start指针大于新节点的End指针，说明新节点中有新增的子元素
    if (oStartIdx > oEndIdx) {
        // 循环结束时，nEndIdx指向的是新增的最后一个元素，拿到它相邻的元素作为参照位置点，就可以把新节点插入到正确的位置
        const before = newCh[nEndIdx + 1] ? newCh[nEndIdx + 1].elm : null
        for(let i = nStartIdx; i <= nEndIdx; i ++) {
            // 如果第二个参数为null，就会添加到最后面
            parentElm.insertBefore(createElm(newCh[i]), before)
        }
    }
    // 如果新节点的Start指针大于End指针，说明新节点中有删除掉的子元素
    else if (nStartIdx > nEndIdx) {
        for (let i = oStartIdx; i <= oEndIdx; i ++) {
            parentElm.removeChild(oldCh[i].elm)
        }
    }
}

这样diff算法的核心实现就算完成了，而在Vue中实现的diff算法跟snabbdom算法是大同小异的，接下来我们可以简单看看Vue中的diff算法是怎么实现的。

七、diff算法在Vue中的实现

首先，大体说一下从Vue实例化开始到最终应用diff算法之间发生了什么事情：
在Vue实例化的时候，会给每个节点都挂上监听器Watcher，当节点上的数据变化是，即触发了setter，这个时候就会调用通知器dep，dep通过notify通知到监听器Watcher。接着Watcher就会通过update函数，对视图进行patch，在patch的过程中就用到了虚拟DOM和diff算法。最终将变化的那部分数据更新到真实DOM上面去。

上面这个过程我们可以分成三个部分：Vue实例化、VNode创建以及diff算法的应用，然后分别讲解这三个部分的具体实现。

  1. Vue实例化
    1）初始化Vue
    一般我们引入Vue的时候，会通过向new Vue()传入参数。这部分代码在src/core/instance/index.ts中： 
    1
    2
    3
    4
    5
    6
    function Vue(options) {
    if (__DEV__ && !(this instanceof Vue)) {
        warn('Vue is a constructor and should be called with the `new` keyword')
    }
    this._init(options)
    }
    这段代码的核心就是将参数透传给init函数，init函数在src/core/instance/init.ts中： 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Vue.prototype._init = function (options?: Object) {
      const vm: Component = this
        
      // 省略一系列其它初始化的代码
        
      if (vm.$options.el) {
        console.log('vm.$options.el:',vm.$options.el);
        vm.$mount(vm.$options.el)
      }
    }
    可以看到其核心就是调用$mount函数，将Vue挂载到传入的根元素上面去

2）Vue实例挂载
$mount的实现则是在src/platforms/web/runtime-with-compiler.ts之中：

1
2
3
4
5
6
7
8
9
10
11
const mount = Vue.prototype.$mount
Vue.prototype.$mount = function (
el?: string | Element,
hydrating?: boolean
): Component {
el = el && query(el)

// 省略一系列初始化以及逻辑判断代码  

return mount.call(this, el, hydrating)
}

可以看到$mount是调用Vue原型上的mount函数，这个在src/platforms/web/runtime/index.ts：
1
2
3
4
5
6
7
Vue.prototype.$mount = function (
    el?: string | Element,
    hydrating?: boolean
): Component {
    el = el && inBrowser ? query(el) : undefined
    return mountComponent(this, el, hydrating)
}

可以看到这个原型mount本质上就是调用了mountComponent，这个函数定义在src/core/instance/lifecycle.ts中：
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
export function mountComponent (
    vm: Component,
    el: ?Element,
    hydrating?: boolean
): Component {
    // 省略一系列其它代码

    let updateComponent
    /* istanbul ignore if */
    if (__DEV__ && config.performance && mark) {
        updateComponent = () => {
        const name = vm._name
        const id = vm._uid
        const startTag = `vue-perf-start:${id}`
        const endTag = `vue-perf-end:${id}`

        mark(startTag)
        const vnode = vm._render()
        mark(endTag)
        measure(`vue ${name} render`, startTag, endTag)

        mark(startTag)
        vm._update(vnode, hydrating)
        mark(endTag)
        measure(`vue ${name} patch`, startTag, endTag)
        }
    } else {
        updateComponent = () => {
        vm._update(vm._render(), hydrating)
        }
    }

    // 实例化一个渲染Watcher，在它的回调函数中会调用 updateComponent 方法  
    new Watcher(vm, updateComponent, noop, {
        before () {
        if (vm._isMounted && !vm._isDestroyed) {
            callHook(vm, 'beforeUpdate')
        }
        }
    }, true /* isRenderWatcher */)
    hydrating = false

    return vm
}

可以看到这段代码的核心就是实例化一个监听器Watcher，它的回调函数会调用updateComponent。而在updateComponent函数中，就会通过vm._render创建VNode，接着通过vm._update将变化的部分更新到真实DOM之中。

  1. VNode创建
    1）_render函数
    _render函数用于将一个实例转化成VNode，它的实现在src/core/instance/render.ts之中

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
     Vue.prototype._render = function (): VNode {
        const vm: Component = this
        const { render, _parentVnode } = vm.$options
        let vnode
        try {
        // 省略一系列代码  
        currentRenderingInstance = vm
        // 调用 createElement 方法来返回 vnode
        vnode = render.call(vm._renderProxy, vm.$createElement)
        } catch (e) {
        handleError(e, vm, `render`){}
        }
        // set parent
        vnode.parent = _parentVnode
        console.log("vnode...:",vnode);
        return vnode
    }

    这里调用了$createElement来创建并返回VNode。

    2）_createElement
    它的实现在src/core/vdom/create-elemenet.ts中：

    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
    export function _createElement (
        context: Component,
        tag?: string | Class<Component> | Function | Object,
        data?: VNodeData,
        children?: any,
        normalizationType?: number
    ): VNode | Array<VNode> {
        
        // 省略一系列非主线代码
        
        if (normalizationType === ALWAYS_NORMALIZE) {
            // 场景是 render 函数不是编译生成的
            children = normalizeChildren(children)
        } else if (normalizationType === SIMPLE_NORMALIZE) {
            // 场景是 render 函数是编译生成的
            children = simpleNormalizeChildren(children)
        }
        let vnode, ns
        if (typeof tag === 'string') {
            let Ctor
            ns = (context.$vnode && context.$vnode.ns) || config.getTagNamespace(tag)
            if (config.isReservedTag(tag)) {
            // 创建虚拟 vnode
            vnode = new VNode(
                config.parsePlatformTagName(tag), data, children,
                undefined, undefined, context
            )
            } else if ((!data || !data.pre) && isDef(Ctor = resolveAsset(context.$options, 'components', tag))) {
            // component
            vnode = createComponent(Ctor, data, context, children, tag)
            } else {
            vnode = new VNode(
                tag, data, children,
                undefined, undefined, context
            )
            }
        } else {
            vnode = createComponent(tag, data, context, children)
        }
        if (Array.isArray(vnode)) {
            return vnode
        } else if (isDef(vnode)) {
            if (isDef(ns)) applyNS(vnode, ns)
            if (isDef(data)) registerDeepBindings(data)
            return vnode
        } else {
            return createEmptyVNode()
        }
    }

    _createElement方法有5个参数：
    context表示VNode上下文环境，它是Component类型。
    tag表示标签，对应snabbdom中的sel，它可以是一个字符串，也可以是一个Component，Function或者Object
    data对应snabbdom中的data，用来保存key、class、attrs等内容，其定义可以在src/core/instance/types/vnode.ts中看到
    children也对应snabbdom中的children，用来保存子节点的信息，一般是一个VNode数组
    这个函数最终返回的就是一个VNode数据结构

    3）VNode
    它的定义在src/core/vdom/vnode.ts之中：

    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
    export default class VNode {
        tag: string | void;
        data: VNodeData | void;
        children: ?Array<VNode>;
        text: string | void;
        elm: Node | void;
        ns: string | void;
        context: Component | void; // rendered in this component's scope
        key: string | number | void;
        componentOptions: VNodeComponentOptions | void;
        componentInstance: Component | void; // component instance
        parent: VNode | void; // component placeholder node

        // strictly internal
        raw: boolean; // contains raw HTML? (server only)
        isStatic: boolean; // hoisted static node
        isRootInsert: boolean; // necessary for enter transition check
        isComment: boolean; // empty comment placeholder?
        isCloned: boolean; // is a cloned node?
        isOnce: boolean; // is a v-once node?
        asyncFactory: Function | void; // async component factory function
        asyncMeta: Object | void;
        isAsyncPlaceholder: boolean;
        ssrContext: Object | void;
        fnContext: Component | void; // real context vm for functional nodes
        fnOptions: ?ComponentOptions; // for SSR caching
        devtoolsMeta: ?Object; // used to store functional render context for devtools
        fnScopeId: ?string; // functional scope id support

        constructor (
            tag?: string,
            data?: VNodeData,
            children?: ?Array<VNode>,
            text?: string,
            elm?: Node,
            context?: Component,
            componentOptions?: VNodeComponentOptions,
            asyncFactory?: Function
        ) {
            this.tag = tag
            this.data = data
            this.children = children
            this.text = text
            this.elm = elm
            this.ns = undefined
            this.context = context
            this.fnContext = undefined
            this.fnOptions = undefined
            this.fnScopeId = undefined
            this.key = data && data.key
            this.componentOptions = componentOptions
            this.componentInstance = undefined
            this.parent = undefined
            this.raw = false
            this.isStatic = false
            this.isRootInsert = true
            this.isComment = false
            this.isCloned = false
            this.isOnce = false
            this.asyncFactory = asyncFactory
            this.asyncMeta = undefined
            this.isAsyncPlaceholder = false
        }
    }

    其中最主要的就是tag、data、children、text、elm和key这六个属性，跟snabbdom的vnode数据结构是一一对应的

  2. diff算法
    通过上述的分析，我们可以知道监听器Watcher在调用update的时候，其实就是调用了updateComponent这个回调函数来创建VNode。而在创建完VNode之后呢，接下来就会调用vm._update函数来完成视图的更新操作。

    1）_update函数
    这个vm._update的实现就在src/core/instance/lifecycle.ts里面：

    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
    Vue.prototype._update = function (vnode: VNode, hydrating?: boolean) {
        const vm: Component = this
        const prevEl = vm.$el
        const prevVnode = vm._vnode
        const restoreActiveInstance = setActiveInstance(vm)
        vm._vnode = vnode
        // Vue.prototype.__patch__ is injected in entry points
        // based on the rendering backend used.
        if (!prevVnode) {
        // initial render
        vm.$el = vm.__patch__(vm.$el, vnode, hydrating, false /* removeOnly */)
        } else {
        // updates
        vm.$el = vm.__patch__(prevVnode, vnode)
        }
        restoreActiveInstance()
        // 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.
    }

    这个函数的中最为重要的就是一个__patch__函数，这个函数对应就是snabbdom中的patch.js，其内部就实现了diff算法。

    2）patch函数
    patch的实现在src/core/vdom/patch.ts中：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    function patch (oldVnode, vnode, hydrating, removeOnly) {
        ......
        if (isUndef(oldVnode)) {
            // 当oldVnode不存在时，创建新的节点
            isInitialPatch = true
            createElm(vnode, insertedVnodeQueue)
        } 
        else {
            // 对oldVnode和vnode进行diff，并对oldVnode打patch  
            const isRealElement = isDef(oldVnode.nodeType)
            if (!isRealElement && sameVnode(oldVnode, vnode)) {
                // patch existing root node
                patchVnode(oldVnode, vnode, insertedVnodeQueue, null, null, removeOnly)
            } 
            ......
        }
    }

    到这里基本逻辑就跟snabbdom算法差不多，存在虚拟节点并且相同就调用patchVnode来比较，不同就是暴力创建。

    3）patchVnode函数
    这个同样在src/core/vdom/patch.ts中定义：

    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
    function patchVnode (oldVnode, vnode, insertedVnodeQueue, ownerArray, index, removeOnly) {
        ...... 
        const elm = vnode.elm = oldVnode.elm
        const oldCh = oldVnode.children
        const ch = vnode.children
        // 如果vnode没有文本节点
        if (isUndef(vnode.text)) {
            // 如果oldVnode的children属性存在且vnode的children属性也存在  
        if (isDef(oldCh) && isDef(ch)) {
            // updateChildren，对子节点进行diff  
            if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue, removeOnly)
        } else if (isDef(ch)) {
            if (process.env.NODE_ENV !== 'production') {
            checkDuplicateKeys(ch)
            }
            // 如果oldVnode的text存在，那么首先清空text的内容,然后将vnode的children添加进去  
            if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '')
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        } else if (isDef(oldCh)) {
            // 删除elm下的oldchildren
            removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        } else if (isDef(oldVnode.text)) {
            // oldVnode有子节点，而vnode没有，那么就清空这个节点  
            nodeOps.setTextContent(elm, '')
        }
        } else if (oldVnode.text !== vnode.text) {
            // 如果oldVnode和vnode文本属性不同，那么直接更新真是dom节点的文本元素
            nodeOps.setTextContent(elm, vnode.text)
        }
        ......
    }

    这个函数的大部分实现也跟snabbdom差不多。当新旧两个VNode都有子节点的时候，就调用updateChildren进行对比，也就是diff算法的核心实现。

    4）updateChildren函数
    同样在src/core/vdom/patch.ts中实现了：

    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
    function updateChildren (parentElm, oldCh, newCh, insertedVnodeQueue, removeOnly) {
        // 为oldCh和newCh分别建立索引，为之后遍历的依据
        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

        // 直到oldCh或者newCh被遍历完后跳出循环
        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, 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)) { // Vnode moved right
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx)
            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, newCh, newStartIdx)
            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]
                : findIdxInOld(newStartVnode, oldCh, oldStartIdx, oldEndIdx)
                if (isUndef(idxInOld)) { // New element
                createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
            } else {
                vnodeToMove = oldCh[idxInOld]
                if (sameVnode(vnodeToMove, newStartVnode)) {
                    patchVnode(vnodeToMove, newStartVnode, insertedVnodeQueue, newCh, newStartIdx)
                    oldCh[idxInOld] = undefined
                    canMove && nodeOps.insertBefore(parentElm, vnodeToMove.elm, oldStartVnode.elm)
                } else {
                    // same key but different element. treat as new element
                    createElm(newStartVnode, insertedVnodeQueue, parentElm, oldStartVnode.elm, false, newCh, newStartIdx)
                }
            }
                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)
        }
    }

    很明显也是用的首尾指针法跟生成key map来实现diff算法，前面把snabbdom算法琢磨透了，这里扫一眼就过了。

参考

snabbdom源码
虚拟DOM 和 diff算法
深入剖析：Vue核心之虚拟DOM
15张图，20分钟吃透Diff算法核心原理，我说的！！！
Vue源码