Virtual-DOM在Vue中的实现--snabbdom源码解读

发表于 分类于 阅读次数：

vue在2.0版本中引入了virtual-DOM，其实现复刻了开源库snabbdom，最近看了一下snabbdom的源码。snabbdom从0.6.0版本开始使用了TypeScript，本文使用的是0.5.4使用JavaScript的版本。

VNode的定义

1
2
3
4
5
6
7
8
9
10
11
module.exports = function(sel, data, children, text, elm) {
    var key = data === undefined ? undefined : data.key;
    return {
        sel: sel, // 可以是custom tag,可以是'div','span',etc,代表这个virtual dom的tag name
        data: data, // virtual dom数据,它们与dom element的prop、attr的语义类似。但是virtual dom包含的数据可以更灵活。
        children: children, // 对应element的children，但是这是vdom的children。vdom的实现重点就在对children的patch上
        text: text, // 对应element.textContent,在children里定义一个string,那么我们会为这个string创建一个textNode
        elm: elm, // 对dom element的引用
        key: key // 用于提示children patch过程
    };
};

h参数/createElement

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
module.exports = function h(sel, b, c) {
    var data = {};
    var children;
    var text;
    var i;
    if (c !== undefined) {
        data = b;
        if (is.array(c)) {
            children = c;
        }
        else if (is.primitive(c)) {
            text = c;
        }
    }
    else if (b !== undefined) {
        if (is.array(b)) {
            children = b;
        }
        else if (is.primitive(b)) {
            text = b;
        }
        else {
            data = b;
        }
    }
    if (is.array(children)) {
        for (i = 0; i < children.length; ++i) {
            if (is.primitive(children[i])) {
                children[i] = VNode(undefined, undefined, undefined, children[i]);
            }
        }
    }
    if (sel[0] === 's' && sel[1] === 'v' && sel[2] === 'g') {
        addNS(data, children, sel);
    }
    return VNode(sel, data, children, text, undefined);
};

snabbdom的patch解析

virtual dom diff

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
return function(oldVnode, vnode) {
    var i, elm, parent;

    // insertedVnodeQueue存在于整个patch过程
    // 用于收集patch中新插入的vnode
    var insertedVnodeQueue = [];

    // 在进行patch之前,我们需要运行prepatch hook
    // cbs是init函数变量,即,这个return语句中函数的闭包
    // 这里,我们不理会lifecycle hook,而只关注vdom diff算法
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    // 如果oldVnode不是vnode(在第一次调用时,oldVnode是dom element)
    // 那么用emptyNodeAt函数来将其包装为vnode
    if (isUndef(oldVnode.sel)) {
        oldVnode = emptyNodeAt(oldVnode);
    }

    // sameVnode是上述“值不值得patch”的核心
    // sameVnode实现很简单,查看两个vnode的key与sel是否分别相同
    // ()=>{vnode1.key === vnode2.key && vnode1.sel === vnode2.
    // 比较语义不同的结构没有意义,比如diff一个'div'和'span'
    // 而应该移除div,根据span vnode插入新的span
    // diff两个key不相同的vnode同样没有意义
    // 指定key就是为了区分element
    // 对于不同key的element,不应该去根据newVnode来改变oldVnode的数据
    // 而应该移除不再oldVnode,添加newVnode
    if (sameVnode(oldVnode, vnode)) {
        // oldVnode与vnode的sel和key分别相同,那么这两个vnode值得去比较
        // patchVnode根据vnode来更新oldVnode
        patchVnode(oldVnode, vnode, insertedVnodeQueue);
    }
    else {
        // 不值得去patch的,我们就暴力点
        // 移除oldVnode,根据newVnode创建elm,并添加至parent中
        elm = oldVnode.elm;
        parent = api.parentNode(elm);

        // createElm根据vnode创建element
        createElm(vnode, insertedVnodeQueue);

        if (parent !== null) {
            // 将新创建的element添加到parent中
            api.insertBefore(parent, vnode.elm, api.nextSibling(elm));

            // 同时移除oldVnode
            removeVnodes(parent, [oldVnode], 0, 0);
        }
    }

    // 结束以后,调用插入vnode的insert hook
    for (i = 0; i < insertedVnodeQueue.length; ++i) {
        insertedVnodeQueue[i].data.hook.insert(insertedVnodeQueue[i]);
    }

    // 整个patch结束,调用cbs中的post hook
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };

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
function patchVnode(oldVnode, vnode, insertedVnodeQueue) {
    var i, hook;

    // 如前,在patch之前,调用prepatch hook,但是这个是vnode在data里定义的prepatch hook,而不是全局定义的prepatch hook
    if (isDef(i = vnode.data) && isDef(hook = i.hook) && isDef(i = hook.prepatch)) {
        i(oldVnode, vnode);
    }

    var elm = vnode.elm = oldVnode.elm;
    var oldCh = oldVnode.children;
    var ch = vnode.children;

    // 如果oldVnode和vnode引用相同,则没必要比较。在良好设计的vdom里,大部分时间我们都在执行这个返回语句。
    if (oldVnode === vnode) return;

    // 如果两次引用不同,那说明新的vnode创建了
    // 与之前一样,我们先看这两个vnode值不值得去patch
    if (!sameVnode(oldVnode, vnode)) {
        // 这四条语句是否与init返回函数里那四条相同？
        var parentElm = api.parentNode(oldVnode.elm);
        elm = createElm(vnode, insertedVnodeQueue);
        api.insertBefore(parentElm, elm, oldVnode.elm);
        removeVnodes(parentElm, [oldVnode], 0, 0);
        return;
    }

    // 这两个vnode值得去patch
    // patch vnode之前,先调用全局的update hook
    // 然后调用vnode.data定义的update hook
    if (isDef(vnode.data)) {
        for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
        i = vnode.data.hook;
        if (isDef(i) && isDef(i = i.update)) i(oldVnode, vnode);
    }

    // patch两个vnode的text和children
    // 查看vnode.text定义
    // vdom中规定,具有text属性的vnode不应该具备children
    // 对于<p>foo:<b>123</b></p>的正确写法是
    // h('p', [ 'foo:', h('b', '123')]), 而非
    // h('p', 'foo:', [h('b', '123')])
    if (isUndef(vnode.text)) {
        // vnode不是text node,我们再查看他们是否有children
        if (isDef(oldCh) && isDef(ch)) {
            // 两个vnode都有children,那么就调用updateChildren
            if (oldCh !== ch) {
                updateChildren(elm, oldCh, ch, insertedVnodeQueue);
            }
        } else if (isDef(ch)) {
            // 只有新的vnode有children,那么添加vnode的children
            if (isDef(oldVnode.text)) {
                api.setTextContent(elm, '');
            }
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue);
        } else if (isDef(oldCh)) {
            // 只有旧vnode有children,那么移除oldCh
            removeVnodes(elm, oldCh, 0, oldCh.length - 1);
        } else if (isDef(oldVnode.text)) {
            // 两者都没有children,并且oldVnode.text不为空,vnode.text未定义,则清空elm.textContent
            api.setTextContent(elm, '');
        }
    } else if (oldVnode.text !== vnode.text) {
        // vnode是一个text node,我们改变对应的elm.textContent
        // 在这里我们使用api.setText api
        api.setTextContent(elm, vnode.text);
    }

    if (isDef(hook) && isDef(i = hook.postpatch)) {
        i(oldVnode, vnode);
    }
}

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
function updateChildren(parentElm, oldCh, newCh, insertedVnodeQueue) {
    var oldStartIdx = 0, newStartIdx = 0;
    var oldEndIdx = oldCh.length - 1;
    var oldStartVnode = oldCh[0];
    var oldEndVnode = oldCh[oldEndIdx];
    var newEndIdx = newCh.length - 1;
    var newStartVnode = newCh[0];
    var newEndVnode = newCh[newEndIdx];
    var oldKeyToIdx, idxInOld, elmToMove, before;

    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
        // 若原始vnode已经被移动，则改变指针，取得新的oldStartVnode和oldEndVnode
        if (isUndef(oldStartVnode)) {
            oldStartVnode = oldCh[++oldStartIdx]; // Vnode has been moved left
        } else if (isUndef(oldEndVnode)) {
            oldEndVnode = oldCh[--oldEndIdx];
        } 
        
        // 如果oldStartVnode和newStartVnode值得比较
        else if (sameVnode(oldStartVnode, newStartVnode)) {
            patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
            oldStartVnode = oldCh[++oldStartIdx];
            newStartVnode = newCh[++newStartIdx];
        }

        // 如果oldEndVnode和newEndVnode值得比较
        else if (sameVnode(oldEndVnode, newEndVnode)) {
            patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
            oldEndVnode = oldCh[--oldEndIdx];
            newEndVnode = newCh[--newEndIdx];
        }

        // 如果oldStartVnode和newEndVnode值得比较，将oldStartVnode向右移动
        else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
            patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
            api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm));
            oldStartVnode = oldCh[++oldStartIdx];
            newEndVnode = newCh[--newEndIdx];
        }
        
        // 如果oldEndVnode, newStartVnode值得比较，将oldEndVnode向左移动
        else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
            patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
            api.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm);
            oldEndVnode = oldCh[--oldEndIdx];
            newStartVnode = newCh[++newStartIdx];
        }
        
        else {
            if (isUndef(oldKeyToIdx)) {
                // 计算key到oldIndex的映射
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
                idxInOld = oldKeyToIdx[newStartVnode.key];
            }
            if (isUndef(idxInOld)) { // New element
                api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm);
                newStartVnode = newCh[++newStartIdx];
            } else {
                elmToMove = oldCh[idxInOld];
                patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
                oldCh[idxInOld] = undefined;
                api.insertBefore(parentElm, elmToMove.elm, oldStartVnode.elm);
                newStartVnode = newCh[++newStartIdx];
            }
        }
    }

    // 如果旧的children数组已经遍历完，新建新的children数组内容。
    if (oldStartIdx > oldEndIdx) {
        before = isUndef(newCh[newEndIdx+1]) ? null : newCh[newEndIdx+1].elm;
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
    }

    // 如果新的children数组遍历完，将剩余旧的children元素删除。
    else if (newStartIdx > newEndIdx) {
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
    }
}

我们先遍历两个数组(while语句),维护四个变量

  • 遍历oldCh的头索引 - oldStartIdx
  • 遍历oldCh的尾索引 - oldEndIdx
  • 遍历newCh的头索引 - newStartIdx
  • 遍历newCh的尾索引 - newEndIdx

当oldStartIdx > oldEndIdx或者newStartIdx > newOldStartIdx的时候停止遍历。

遍历过程中有五种比较

前四种比较

  • oldStartVnode和newStartVnode,两者elm相对位置不变,若值得(sameVnode)比较,这patch这两个vnode
  • oldEndVnode和newEndVnode,同上,elm相对位置不变,做相同patch检测
  • oldStartVnode和newEndVnode,如果oldStartVnode和newEndVnode值得比较,说明oldCh中的这个- oldStartVnode.elm向右移动了。那么执行api.insertBefore(parentElm, oldStartVnode.elm, api.nextSibling(oldEndVnode.elm))调整它的位置
  • oldEndVnode和newStartVnode,同上,但这是oldVnode.elm向左移,需要调整它的位置

最后一种比较

利用vnode.key,在ul>li*n的结构里,我们很有可能使用key来标志li的唯一性,那么我们就会来到最后一种情况。这个时候,我们先产生一个index-key表(createKeyToOldIdx),然后根据这个表来进行更改。

更改规则

  • 如果newVnode.key不在表中,那么这个newVnode就是新的vnode,将其插入
  • 如果newVnode.key在表中,那么对应的oldVnode存在,我们需要patch这两个vnode,并在patch之后,将这个oldVnode置为undefined(oldCh[idxInOld] = undefined),同时将oldVnode.elm位置变换到当前oldStartIdx之前,以免影响接下来的遍历

遍历结束后,检查四个变量,对移除剩余的oldCh或添加剩余的newCh

参考文献