Virtual DOM库snabbdom核心72行代码深度解析

1,153 阅读8分钟

为什么选择snabbdom

如果要选择一个开源项目来理解virtual domsnabbdom是一个不错的选择。snabbdom有以下几个优势。

1、VueJS的 virtual dom 部分基于snabbdom改造,理解了snabbdom有利于理解VueJS

2、snabbdom足够简洁、成熟,已经被用于多个开源项目。

3、snabbdom使用typescript,阅读代码过程中有类型辅助(当然,不习惯typescript的话可能是个劣势,不如看之前的版本)。

为什么说只有72行

相比VueJS编译后代码12000行,snabbdom编译后代码只有500行。而源代码snabbdom.ts为319行。而这319行代码中,最难理解的,莫过于用来更新节点的updateChildren函数。这个函数,只有72行。之所以罗列这么多数字,是想通过数字对比说明,阅读源码要分主次,主要的部分,哪怕多花些时间,也要弄懂,否则很可能是一知半解。

有不少网友都对snabbdom的源码做过详细的分析,比如这篇,对updateChildren函数逐行做了注解。但是,看了这些注解,我依然难以理解这些代码作为一个整体的设计思路。本文试图条分缕析updateChildren的实现思路,以期更全面地理解其中精髓。

Tips: 如果你还没有看过snabbdom源码,建议从它的项目说明开始,了解它的接口设计和使用方法,通读snabbdom.ts后再看下文,否则可能不知道下文在说什么。

阅读代码准备工作

下文只是摘出了snabbdom.ts文件中updateChildren的部分进行分析,需要对照完整代码进行查看。可以将代码库下载到本地:

git clone git@github.com:snabbdom/snabbdom.git
git reset d524860ad764cc90d66ba82816f35be73230cf98 --hard

也可以直接在github查看

updateChildren

1、updateChildren只在patchVnode中调用:

updateChildren(elm, oldCh, ch, insertedVnodeQueue)

调用时,已经保证了oldChch处于同一个dom层级,也就是说,要么用ch完全替换oldCh,要么就是部分替换。

2、那么如何定义updateChildren呢?这个函数需要更新某个元素(parentElm)的子节点,已知旧的虚拟子节点(oldCh)和新的虚拟子节点(newCh),需要用最优化的方式做替换。函数定义如下:

function updateChildren (parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue) {
}

按理说,前三个参数就够了。insertedVnodeQueue是用来做什么的?最后再说,先不管。到这,咱们可以把updateChildren要解决的问题理解为:两个数组的diff算法。每个数组的元素类型为Vnode

3、函数主体部分,需要循环对比节点,以确定哪些节点该增、该减、该移、该改。

function updateChildren (parentElm: Node,
    oldCh: VNode[],
    newCh: VNode[],
    insertedVnodeQueue: VNodeQueue) {
    //A.定义局部变量
    let oldStartIdx = 0, newStartIdx = 0;
    let oldEndIdx = oldCh.length - 1;
    let newEndIdx = newCh.length - 1;
    //...
    
    //B.循环对比
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {}
    
    //C.处理循环中剩下的节点
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {}
}

B部分,只要oldCh或者newCh(后面简称新旧数组)中有一个数组的元素全部比对完,循环就结束。结束时可能另一个数组还没有比对完,所以才会有C部分的代码。

4、细看B部分循环体。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVnode == null) {//B1
    } else if (oldEndVnode == null) {//B2
    } else if (newStartVnode == null) {//B3
    } else if (newEndVnode == null) {//B4
    } else if (sameVnode(oldStartVnode, newStartVnode)) {//B5
    } else if (sameVnode(oldEndVnode, newEndVnode)) {//B6
    } else if (sameVnode(oldStartVnode, newEndVnode)) {//B7
    } else if (sameVnode(oldEndVnode, newStartVnode)) {//B8
    } else {}//B9
}

每一轮对比,分9种情况。其中B1-B4是新旧数组首尾出现无效元素的情况(为什么会无效?后面解释);B5-B8是指新旧数组首尾元素两两对比出现相同元素的情况,这种情况,元素对应的dom应该复用。相同元素,是指keysel属性都相等的元素。

B1-B8属于特殊情况,优先处理。B9对应dom节点的乱序改变,或者多种改变的组合情况。

5、先看B9部分。

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVnode == null) {//B1-B8
    } else {//B9
        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!);
        } else {
          elmToMove = oldCh[idxInOld];
          if (elmToMove.sel !== newStartVnode.sel) {
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!);
          } else {
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any;
            api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);
          }
        }
        newStartVnode = newCh[++newStartIdx];
    }
}

key为依据,检查newStartVnode.key是否存在于老数组中,如果不存在,表示是新元素;如果存在,而且元素的sel属性不相等,也视为新元素;否则就是相同元素,可以复用。sel是由tag/id/class组成的字符串,如:div#container.visible.visible-xs

6、B9复用的元素

对于B9中复用的元素,执行如下操作:

patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
oldCh[idxInOld] = undefined as any;
api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);

第一行代码。如果按字面意义理解patchVnode:用newStartVnodeelmToMove打补丁。其实不对,patchVnode方法中所有的修改是针对newStartVnode的,elmToMove只是拿来做属性对比和Dom节点复用的。updateChildren完成后,oldCh就没有存在的必要了。理解这一点是有必要的。

第二行代码。oldCh[idxInOld] = undefined as any,此处是将旧数组中的该元素销毁(注意不是删除),改成null as any也是可以的。加as any是为了适配Vnode类型,oldCh是个Vnode数组。回头看第4部分的B1-B2要做null判断,就是因为此处将oldCh中的元素置为undefined了。对比的时候,使用oldStartVnode == null,等同于undefined == null,是成立的。

为什么不直接将这个元素删掉呢?保持这个元素,是为了保证数组的元素恒定不变,从而不影响while的正常运行,同时标记为undefined方便了B1-B4的处理。

第三行代码。api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!);。这是指将oldCh数组中的elmToMove对应的dom节点,移到oldStartVnode对应dom节点的前面。而第一行代码,已将elmToMove.elm赋值给了新数组的第一个元素,即newStartVnode。这样一来,newStartVnodenewCh中的索引,和newStartVnode.elm在其兄弟dom节点中的索引,能保持一致。

同时也可以看到,这三行代码在操作dom节点位置的同时,并没有更改老数组中的elmToMove元素的位置,会不会有问题?不会。因为updateChidren执行完成后,oldCh就没有存在的价值了,同时也为了保证oldCh在循环过种中的稳定。

7、再看B1-B8

在整个while循环中,如果碰到了相等的元素,则执行patchNode(修改虚拟dom,使newCh中的元素与实际dom节点建立关联),必要时执行api.insertBefore(修改真实dom)操作;如果碰到了新元素,则只执行api.insertBefore操作。

B1-B4:新旧数组两端出现空元素时,忽略并进入下一次循环。

if (oldStartVnode == null) {//B1
    oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
} else if (oldEndVnode == null) {//B2
    oldEndVnode = oldCh[--oldEndIdx];
} else if (newStartVnode == null) {//B3
    newStartVnode = newCh[++newStartIdx];
} else if (newEndVnode == null) {//B4
    newEndVnode = newCh[--newEndIdx];
}

B5:新旧数组首位元素相等时,只需要在原位置更新虚拟dom和真实dom,不需要移动位置。

} else if (sameVnode(oldStartVnode, newStartVnode)) {//B5
    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
    oldStartVnode = oldCh[++oldStartIdx];
    newStartVnode = newCh[++newStartIdx];
}

B6:新旧数组末位元素相同时,只需要在原位置更新虚拟dom和真实dom,不需要移动位置。

} else if (sameVnode(oldEndVnode, newEndVnode)) {//B6
    patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
    oldEndVnode = oldCh[--oldEndIdx];
    newEndVnode = newCh[--newEndIdx];
}

B7:新数组末位元素和旧数组中首位元素相等,依据新数组的顺序,应该将旧数组首位元素对应的dom节点移至其他dom节点的后面。注意代码用api.insertBefore实现了insertAfter的功能,因为oldEndVnode.elm!加了一层api.nextSibling

} else if (sameVnode(oldStartVnode, newEndVnode)) {//B7
    patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
    api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!));
    oldStartVnode = oldCh[++oldStartIdx];
    newEndVnode = newCh[--newEndIdx];
}

B8:与B7相反。新数组首位元素和旧数组中末位元素相等,依据新数组的顺序,应该将旧数组末位元素对应的dom节点移至其他dom节点的前方。

} 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];
}

8、看函数最后一部分代码

//C.处理循环中剩下的节点
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);
  }
}

while循环后,如果旧数组先完成比对(oldStartIdx > oldEndIdx),说明新数组中的其他元素都是新增的,需要创建对应的真实dom,并与这些元素关联(addVnodes);否则,旧数组中的剩余元素应该被删除(removeVnodes),removeNodes也会同时删除对应的真实dom节点。

insertedVnodeQueue

insertedVnodeQueue用于执行勾子(hook)中的insert方法,但它是在一次patch完成所有dom节点的更新后,一起执行。

总结

1、updateChidren实际上就是virtual dom diff算法的实现,做到了尽可能多地复用真实dom。

2、同时让两个数组头尾收缩的循环方式,十分巧妙;

3、while循环条件的设计思路十分清晰,B1-B4,B5-B8,B9各思其职。但B1-B4与B9有直接关联,阅读代码的时候要来回比较才能明白;

4、尽管本文已经写得比较多,仍有不少值得分析的地方没来得及写。比如while循环两数组,理论上是如何保证顺序的?怎样将测试用例用可视化的方式来演示?

扩展阅读

React diff算法,思路基本上是一样的。