vue源码——snabbdom虚拟DOM(转载)

原文

前言

snabbdom是一个虚拟dom算法库,它的特点是效率高、可扩展,许多开源项目采用了这种算法,例如vue。本文试图还原虚拟dom的diff原理(仅限于snabbdom算法)。

虚拟DOM

什么是虚拟dom

首先需要了解什么是虚拟dom,虚拟dom是真实dom的简单映射。我们知道一个真实dom的属性是十分繁多的,但是表示一个真实dom仅仅需要一部分属性就够了。对于一个真实dom,只要我们清楚它的选择器、它的子节点以及它的“数据”(属性、样式、类、事件等),我们就可以利用一个对象(即虚拟dom)来描述这个真实的dom节点,如下:

class Vnode {
constructor({sel, data, children, text, key}) {
// 选择器
this.sel = sel;
// key
this.key = key;
// 保存属性、样式等
this.data = data;
// 子节点
this.children = children;
// 对应的真实dom节点
this.elm = null;
// 文本节点
this.text = text;
}
}

举个例子

<ul>
<li>a</li>
<li>b</li>
</ul>

可以被表示为:

new Vnode({
sel: 'ul',
children: [
new Vnode({
sel: 'li',
children: [new Vnode({text: a})]
}),
new Vnode({
sel: 'li',
children: [new Vnode({text: b})]
})
]
})

为什么需要虚拟dom

对于前端mvc模型,当model改变时相应的view需要更新,一种最简单的方法是只要model发生了改变就利用模板引擎更新整个view,这在页面简单时是极好的,但是当面对复杂应用时代价过大,其需要重新渲染dom树,这可是很耗时的。合理的操作是哪里改变了重新渲染哪里,通过比较新旧虚拟dom树可以找出相同和不同,相同的地方就复用真实dom节点,不同的地方就对真实dom节点进行增加、删除、移动等操作,这样一来就大大提高了效率。

虚拟dom的diff

在谈到虚拟dom的diff时有个前提:diff只发生在相同的层级。这是因为跨越层级的dom增添、删除、移动并不常见,一般都是兄弟节点之间的位置发生变化。

首先需要判断两个虚拟节点是否为samaVnode,假如是sameVnode则保留旧的真实dom并对新旧虚拟节点的children进行diff,否则删除掉旧虚拟节点对应的真实dom并替换为新虚拟节点对应的真实dom。如下:

if (sameVnode(oldVnode, vnode)) {
patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else {
elm = oldVnode.elm as Node;
parent = api.parentNode(elm);

createElm(vnode, insertedVnodeQueue);

if (parent !== null) {
api.insertBefore(parent, vnode.elm as Node, api.nextSibling(elm));
removeVnodes(parent, [oldVnode], 0, 0);
}
}

sameVnode如下定义:

function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}

sameVnode需要满足两个条件:

新旧虚拟节点children的diff是整个虚拟dom算法的核心,首先解决以下几个特殊情况:

  • 新虚拟dom有children,旧虚拟dom没有children
    处理方法:假如旧虚拟dom的text属性有定义,说明旧真实dom节点有且仅有文本子节点,需要先清除文本节点,然后将新虚拟节点children对应的真实节点添加到父节点

    // oldVnode  旧虚拟节点
    // vnode 新虚拟节点
    // oldCh 旧虚拟节点的子虚拟节点
    // ch 新虚拟节点的子虚拟节点
    // elm 新旧虚拟节点对应的真实节点
    } else if (isDef(ch)) {
    if (isDef(oldVnode.text)) api.setTextContent(elm, '');
    addVnodes(elm, null, ch as Array<VNode>, 0, (ch as Array<VNode>).length - 1, insertedVnodeQueue);
    }
  • 旧虚拟dom有children,新虚拟dom没有children

解决方法:删除掉旧虚拟节点children对应的真实节点即可

} else if (isDef(oldCh)) {
removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
}

  • 旧虚拟节点text属性有定义,新虚拟节点text属性没定义且没有children
    解决方法:说明旧节点有且仅有文本子节点,新节点为空节点,删除旧节点文本内容即可

    api.setTextContent(elm, '');
  • 就虚拟节点的text属性有定义,新虚拟节点的text属性有定义
    解决方法:说明新旧节点都有且仅有文本子节点,直接比较文本内容,不相同替换即可

    } else if (oldVnode.text !== vnode.text) {
    api.setTextContent(elm, vnode.text as string);
    }

以上是新旧虚拟dom子节点的四种特殊情况,还剩下一种普遍情况即:新旧虚拟dom均有children:

if (isDef(oldCh) && isDef(ch)) {
if (oldCh !== ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue);
}

各种虚拟dom算法的差别在于updateChildren方法实现的不同,snabbdom算法的特点是给新旧children分别提供了头尾两个指针,diff过程中头尾指针均向中间靠拢,当任一children的头指针超过尾指针则diff过程结束。以下图这个例子做参照,相同字母代表两个虚拟dom是sameVnode:

具体的指针移动方式又可以分为以下6种情况:

  • 新children(下文记为ch)的头与旧children(下文记为oldCh)的头是sameVnode
    解决方法:这种情况说明oldch头指针指向的虚拟dom的真实节点可原地复用,只需将oldch和ch的头指针分别向后移动一位即可,移动后如下:

  • ch的尾与oldCh的尾是sameVnode
    解决方法:这种情况说明oldch尾指针指向的虚拟dom的真实节点可原地复用,只需将oldch和ch的尾指针分别向前移动一位即可,移动后如下:

  • ch的尾与oldCh的尾是sameVnode
    解决方法:这种情况说明oldch尾指针指向的虚拟dom的真实节点可原地复用,只需将oldch和ch的尾指针分别向前移动一位即可,移动后如下:

  • oldCh的尾与ch的头是sameVnode
    解决方法:与上面相似,oldCh尾指针指向的虚拟dom的真实节点可以复用,但是其被移动到了oldCh头指针指向虚拟dom的真实节点的前面,这时需要将oldCh的尾指针向前移动一位,ch的头指针向后移动一位,移动后如下:

  • 在oldCh中可以找到与ch的头是sameVnode的虚拟节点(此节点记为moveVnode)
    解决方法:这种情况意味着moveVnode对应的真实节点可以被复用,且移动到了oldCh头指针指向虚拟dom的真实节点的前面,此时需要将ch的头指针向后移动一位,同时将moveVnode设置为null,因为其已经被复用了,当头指针或者尾指针再指向它时需要跳过。移动后如下:

  • 不符合以上五种情况
    解决方法:当以上五种情况均不符合时,说明ch头指针指向的虚拟dom是一个全新的节点,也即在oldCh中不能找到可复用的节点,此时应当根据ch头指针指向的虚拟dom创建真实dom,并插入到oldCh头指针指向真实节点的前面。移动后如下:

以上分别对应了6种指针移动的方式,同时可以发现此时ch的头指针已经超越了尾指针,说明diff已经结束,但是此时oldCh的头指针依然小于尾指针,这说明在oldCh头指针和尾指针之间的虚拟dom对应的真实dom不能够被复用,需要删除掉。想象一下,假如oldCh的头指针超越了尾指针,而ch的头指针仍然小于尾指针,这说明了原有的dom节点全部可以复用,且ch的头指针和尾指针之间的虚拟dom代表了新的节点,需要被创建并插入到原有dom中。

下面是snabbdom中updateChildren的代码,添加了部分注释:

function updateChildren(parentElm: Node,
oldCh: Array<VNode>,
newCh: Array<VNode>,
insertedVnodeQueue: VNodeQueue) {
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: any;
let idxInOld: number;
let elmToMove: VNode;
let before: any;

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
// 下面4行代码我认为没有意义 不可能出现oldStartVnode或者oldEndVnode为null的情况
if (oldStartVnode == null) {
oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
} 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, 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);
api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
oldStartVnode = oldCh[++oldStartIdx];
newEndVnode = newCh[--newEndIdx];
// 对应上文第四种情况
} else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
oldEndVnode = oldCh[--oldEndIdx];
newStartVnode = newCh[++newStartIdx];
} else {
if (oldKeyToIdx === undefined) {
oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
}
idxInOld = oldKeyToIdx[newStartVnode.key as string];
// 新的虚拟节点
if (isUndef(idxInOld)) { // New element
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
newStartVnode = newCh[++newStartIdx];
} else {
elmToMove = oldCh[idxInOld];
// key和sel均相同时才是sameVnode
// 对应上文第五种情况
if (elmToMove.sel !== newStartVnode.sel) {
api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
// 新的虚拟节点
} else {
patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined as any;
api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
}
newStartVnode = newCh[++newStartIdx];
}
}
}
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
// 原节点全部被复用
if (oldStartIdx > oldEndIdx) {
before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue);
// 原节点被部分复用
} else {
removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx);
}
}
}