Snabbdom 底层Diff算法详解

Vue2.0 的Virtual DOM 是基于 Snabbdom 改造的，针对 Children 的 Diff 过程，做了一下详细的过程分析以及演示。

前言

浏览器在渲染 DOM 元素的时候，是非常‘昂贵的’，在进行 DOM 更新的时候，针对复杂 DOM 的局部更新，为了节省浏览器的开支，避免不必要的更新，这个时候就需要通过Diff 比较来决定更新哪些 DOM 元素，当然，并不是所有的情况都能使 Virtual DOM 比原生 DOM 操作要快，这里我就不过多阐述了，好了，进入主题

1.0 Snabbdom Diff 方式

Snabbdom 在进行 Diff 比较的时候只针对同层级进行比较，而不会进行跨层级比较，也就是说，我不会管你当前的 Children 是否一致，这里我只关心你和他。Snabbdom 更新DOM的方式是 先移后添加或删除， Diff 比较是双向由外向里进行比较。

Diff方式

为了方便演示 Snabbdom 的 Diff 的过程，这里我以一个 DOM 更新的案例为大家讲解

假设当前 DOM parentElm 有9个 DOM元素，
这里我用数组模拟oldCh = [null, "A", "B", "C", "D", "E", "F", "G", null]表示，
其中数组的每一个元素代表一个子节点DOM，其中两个null，表示已经移除了，这里加入null 的目的是为了后续分析源码流程所使用。

parentElm DOM

更新后DOM parentElm有11个DOM元素，
这里我用数组模拟newCh = [null, "A", "F", "E", "M", "O", "I", "E", "B", "G", null]表示，
其中数组的每一个元素代表一个子节点DOM，其中两个null，表示已经移除了，这里加入null 的目的是为了后续分析源码流程所使用。

2.0 Snabbdom Diff 过程

首先，我用一张图来解释Snabbdom 在找出差异之前是如何进行Diff 比较的

找出差异前

Snabbdom 在找出差异之前，每一轮的比较是需要经过8项条件比较的，具体比较【条件】如下：

【1】.判断 oldCh 第一个节点元素是不是空的，如果是空的表示 DOM 已经移除，接着进行下一轮比较
【2】.判断 oldCh 最后一个节点元素是不是空的，如果是空的表示 DOM 已经移除，接着进行下一轮比较
【3】.判断 newCh 第一个节点元素是不是空的，如果是空的表示 DOM 已经移除，接着进行下一轮比较
【4】.判断 newCh 最后一个节点元素是不是空的，如果是空的表示 DOM 已经移除，接着进行下一轮比较。
【5】.判断 oldCh 与 newCh 第一个节点元素是不是相同，如果相同我们接着进行下一轮比较
【6】.判断 oldCh 与 newCh 最后一个节点元素是不是相同，如果相同我们接着进行下一轮比较
【7】.判断 oldCh 第一个节点元素与 newCh 的最后一个节点元素是否相同，如果相同，就将oldCh 第一个节点元素进行移动，具体如何移动，后面我会详细阐述说明。
【8】.判断 oldCh 最后一个节点元素与 newCh 的第一个节点元素是否相同，如果相同，就将oldCh 最后一个节点元素进行移动，具体如何移动，后面我会详细阐述说明。

由于 Diff 比较过程是双向由外向里进行比较，所以为了比较过程这里我们设置几个记录值

为了记录比较过程这里我们设置几个记录值
oldSIdx ：初始值为0，表示当前oldCh 比较队列的初始的节点位置
newSIdx ：初始值为0，表示当前newCh 比较队列的初始的节点位置
oldEIdx ：初始值为oldCh.length-1，表示当前oldCh 比较队列的末尾的节点位置
newEIdx ：初始值为newCh.length-1，表示当前newCh 比较队列的末尾的节点位置
oldSnode ：初始值为oldCh[0]，表示当前oldCh 比较队列的初始节点
oldEnode ：初始值为oldCh[oldEIdx]，表示当前oldCh 比较队列的末尾节点
newSnode ：初始值为newCh[0]，表示当前newCh 比较队列的初始节点
newEnode ：初始值为newCh[newEIdx]，表示当前newCh 比较队列的末尾节点

每一轮的Diff 执行条件：oldSIdx <= oldEIdx && newSIdx <= newEIdx，也就是说，当两边的比较有一方的元素已经全部比较完毕，那么Diff中止

初始状态：

初始状态

第1轮Diff 比较：满足条件【1】 oldCh 第一个节点元素是空，执行以下步骤，根据结果接着进行下一轮比较

执行： oldSIdx位置加1，oldSnode指向下一个节点> oldSnode=[++oldSIdx]

第1轮执行过程

第1轮Diff 比较结束后，oldCh 初始记录点oldSIdx索引+1，由0变为1，oldSnode指向下一个节点，由null变为A。

第1轮比较结束后

第2轮Diff 比较：满足条件【2】 oldCh 最一个节点元素是空，，执行以下步骤，根据结果接着进行下一轮比较

执行： oldEIdx位置减1，oldEnode指向上一个节点> oldEnode=[--oldEIdx]

第2轮执行过程

第2轮Diff 比较结束后，oldCh 末尾记录点oldEIdx索引-1，由8变为7，oldEnode指向下一个节点，由null变为G。

第2轮比较结束后

第3Diff 轮比较：满足条件【3】 newCh 第一个节点元素是空，执行以下步骤，根据结果接着进行下一轮比较

执行： newSIdx位置加1，newSnode指向下一个节点> newSnode=[++newSIdx]

第3轮执行过程

第3轮Diff 比较结束后，newCh 初始记录点newSIdx索引+1，由0变为1，newSnode指向下一个节点，由null变为A。

第3轮比较结束后

第4轮Diff 比较：满足条件【4】 newCh 最一个节点元素是空，执行以下步骤，根据结果接着进行下一轮比较

执行： newEIdx位置减1，newEnode指向上一个节点> newEnode=[--newEIdx]

第4轮执行过程

第4轮Diff 比较结束后，newCh 末尾记录点newEIdx索引-1，由10变为9，newEnode指向下一个节点，由null变为G。

第4轮比较结束后

第5轮Diff 比较：满足条件【5】 oldCh 与 newCh 第一个节点元素相同，执行以下步骤，根据结果接着进行下一轮比较

执行：
oldSIdx位置加1，oldSnode指向下一个节点> oldSnode=[++oldSIdx]
newSIdx位置加1，newSnode指向下一个节点> newSnode=[++newSIdx]

第5轮执行过程

第5轮Diff 比较结束后：
oldCh 初始记录点oldSIdx索引+1，由1变为2，oldSnode指向下一个节点，由A变为B。
newCh 初始记录点newSIdx索引+1，由1变为2，newSnode指向下一个节点，由A变为F。

第5轮比较结束后

第6轮Diff 比较：满足条件【6】 oldCh 与 newCh 最后一个节点元素相同，执行以下步骤，根据结果接着进行下一轮比较

执行：
oldEIdx位置减1，oldEnode指向上一个节点> oldEnode=[--oldEIdx]
newEIdx位置减1，newEnode指向上一个节点> newEnode=[--newEIdx]

第6轮执行过程

第6轮Diff 比较结束后：
oldCh 末尾记录点oldEIdx索引-1，由7变为6，oldEnode指向上一个节点，由G变为F。
newCh 末尾记录点newEIdx索引-1，由9变为8，newEnode指向上一个节点，由G变为B。

第6轮比较结束后

看到这里，不知道各位有没有发现，每一轮的比较，在满足Diff算法的前 6 种判断条件下，父节点parentElm 是没有发生任何变化的，那么，接下来就是见证奇迹的时刻！

第7轮Diff 比较：满足条件【7】 oldCh 第一个节点元素与 newCh 最后一个节点元素相同，执行以下步骤，根据结果接着进行下一轮比较

执行：
我们首先将当前的oldSnode（B）元素移动插入到当前oldEnode（F）元素的后面
oldSIdx位置加1，oldSnode指向下一个节点> oldSnode=[++oldSIdx]
newEIdx位置减1，newEnode指向上一个节点> newEnode=[--newEIdx]

第7轮执行过程

第7轮Diff 比较结束后：
parentElm更新DOM，将当前的oldSnode（B）元素移动插入到当前oldEnode（F）元素的后面
oldCh 初始记录点oldSIdx索引+1，由2变为3，oldSnode指向下一个节点，由B变为C。
newCh 末尾记录点newEIdx索引-1，由8变为7，newEnode指向上一个节点，由B变为E。

第7轮比较结束后

第8轮Diff 比较：满足条件【8】 oldCh 最后一个节点元素与 newCh 第一个节点元素相同，执行以下步骤，根据结果接着进行下一轮比较

执行：
我们首先将当前的oldEnode（F）元素插入到当前oldSnode（C）元素的前面
oldEIdx位置减1，oldEnode指向上一个节点> oldEnode=[--oldEIdx]
newSIdx位置加1，newSnode指向下一个节点> newSnode=[++newSIdx]

第8轮执行过程

第8轮Diff 比较结束后：
parentElm更新DOM，将当前的oldEnode（F）元素插入到当前oldSnode（C）元素的前面
oldCh 末尾记录点oldEIdx索引-1，由6变为5，oldEnode指向上一个节点，由F变为E。
newCh 初始记录点newSIdx索引+1，由2变为3，newSnode指向下一个节点，由F变为E。

第8轮比较结束后

第9轮Diff 比较：满足条件【6】 oldCh 与 newCh 最后一个节点元素相同，执行以下步骤，根据结果接着进行下一轮比较

执行：
oldEIdx位置减1，oldEnode指向上一个节点> oldEnode=[--oldEIdx]
newEIdx位置减1，newEnode指向上一个节点> newEnode=[--newEIdx]

第9轮执行过程

第9轮Diff 比较结束后：
oldCh 末尾记录点oldEIdx索引-1，由5变为4，oldEnode指向上一个节点，由E变为D。
newCh 末尾记录点newEIdx索引-1，由7变为6，newEnode指向上一个节点，由E变为I。

第9轮比较结束后

看到这里，经过以上每一轮的比较，基本上前 8 种Diff条件都已经差不多全部执行了，接下来的就是我们找出差异之后的DOM更新了。

第10轮Diff 比较：前 8 种Diff条件都不满足，则需要新增节点
执行以下步骤，根据结果接着进行下一轮比较

执行：
parentElm更新DOM，将当前的oldEnode（E）元素插入到当前oldSnode（C）元素的前面
newSIdx位置+1，newSnode指向下一个节点> newSnode=[++newSIdx]

第10轮执行过程

第10轮Diff 比较结束后：
parentElm更新DOM，将当前的oldEnode（E）元素插入到当前oldSnode（C）元素的前面
newCh 初始记录点newSIdx索引+1，由3变为4，newSnode指向下一个节点，由E变为M。

第10轮比较结束后

第11轮Diff 比较：前 8 种Diff条件都不满足，则需要新增节点
执行以下步骤，根据结果接着进行下一轮比较

执行：
parentElm更新DOM，将当前的oldEnode（M）元素插入到当前oldSnode（C）元素的前面
newSIdx位置+1，newSnode指向下一个节点> newSnode=[++newSIdx]

第11轮执行过程

第11轮Diff 比较结束后：
parentElm更新DOM，将当前的oldEnode（M）元素插入到当前oldSnode（C）元素的前面
newCh 初始记录点newSIdx索引+1，由4变为5，newSnode指向下一个节点，由M变为O。

第11轮比较结束后

;

第12轮Diff 比较：前 8 种Diff条件都不满足，则需要新增节点
执行以下步骤，根据结果接着进行下一轮比较

执行：
parentElm更新DOM，将当前的oldEnode（O）元素插入到当前oldSnode（C）元素的前面
newSIdx位置+1，newSnode指向下一个节点> newSnode=[++newSIdx]

第12轮执行过程

第12轮Diff 比较结束后：
parentElm更新DOM，将当前的oldEnode（O）元素插入到当前oldSnode（C）元素的前面
newCh 初始记录点newSIdx索引+1，由5变为6，newSnode指向下一个节点，由M变为O。

第12轮比较结束后

第13轮Diff 比较：前 8 种Diff条件都不满足，则需要新增节点
执行以下步骤，根据结果接着进行下一轮比较

执行：
parentElm更新DOM，将当前的oldEnode（I）元素插入到当前oldSnode（C）元素的前面
newSIdx位置+1，newSnode指向下一个节点> newSnode=[++newSIdx]

第13轮执行过程

第13轮Diff 比较结束后：
parentElm更新DOM，将当前的oldEnode（I）元素插入到当前oldSnode（C）元素的前面
newCh 初始记录点newSIdx索引+1，由6变为7，newSnode指向下一个节点，由I变为E。
此时 newSIdx > newEIdx，已经不能满足下一轮Diff 比较的条件，Diff 比较比较结束

第13轮最后一次比较结束

经过13轮的新旧子节点Diff比较，parentElm通过将旧节点移动，新节点增加，进行了DOM的更新，接下来就是根据最终oldCh 与newCh剩余情况进行parentElm的删除或者新增。
如果当前newCh[newSIdx,newEIdx]有剩余，说明还有需要新增的元素，那么我们根据剩余的节点区间，依次插入到最终比较的newEnode后面。
如果当前oldCh[oldSIdx,oldEIdx]有剩余，说明这些元素是需要删除的，那么我们根据剩余的节点区间，依次删除。

old节点删除过程

最终DOM局部更新完成

3.0 代码模拟过程

基于Snabbdom，通过数组来表示DOM节点元素，这里我稍微改造了一下，基于数组操作来模拟DOM的更新


/**
 * author：Echonessy
 * des:
 * date:2020.07.05
 * target: Diff 算法模拟
 * */


let oldCh = [null,"A","B","C","D","E","F","G",null];
let newCh = [null,"A","F","E","M","O","I","E","B","G",null];
// let oldCh = [null,"A","B","C","D","E","F","G",null];
// let newCh = [null,"A","F","C","D","E","M","O","I","E","B","G",null];
let parentElm = oldCh.slice();
diff(parentElm,oldCh,newCh);
// 判断节点是否相同
export function same(vnode1, vnode2) {
    return vnode1 === vnode2
}

// 模拟DOM节点插入与移动
function insertBerfore(parent,newNode,referenceNode,order) {
    switch (order) {
        case 'left':parent.splice(parent.indexOf(referenceNode),0,newNode);parent.splice(parent.indexOf(newNode.split('-')[1]),1);break;
        case 'right':parent.splice(parent.indexOf(referenceNode),0,newNode);parent.splice(parent.lastIndexOf(newNode.split('-')[1]),1);break;
        case 'diff':parent.splice(parent.indexOf(referenceNode.indexOf('-')!=-1?referenceNode.split('-')[1]:referenceNode),0,newNode);break;
        case 'add':parent.splice(parent.lastIndexOf(referenceNode),0,newNode);break;
    }
}

// 移除vNode
export function removeVnodes(parentElm,vnodes,startIdx,endIdx){
    // 循环vnodes
    for (; startIdx <= endIdx; ++startIdx) {
        let ch = vnodes[startIdx];
        if (ch != null) {
            var index = parentElm.indexOf(ch);
            parentElm.splice(index, 1)
        }
    }
}
// 添加vNode
function addVnodes(parentElm,before,vnodes,startIdx,endIdx) {
    for (; startIdx <= endIdx; ++startIdx) {
        const ch = vnodes[startIdx];
        if (ch != null) {
            insertBerfore(parentElm,'new-'+ch,before,'add')
        }
    }
}
// diff 过程
function diff(parentElm,oldCh,newCh) {
    console.log('初始')
    console.log(oldCh)
    console.log(newCh)
    console.log(parentElm)
    let oldSIdx = 0, newSIdx = 0;
    let oldEIdx = oldCh.length - 1;
    let oldSnode = oldCh[0];
    let oldEnode = oldCh[oldEIdx];
    let newEIdx = newCh.length - 1;
    let newStnode = newCh[0];
    let newEnode = newCh[newEIdx];
    let conunt = 0; // 计数器，记录循环次数
    // 两数组比较结束之前，循环调用Diff
    while (oldSIdx <= oldEIdx && newSIdx <= newEIdx){
        if (oldSnode == null) {
            oldSnode = oldCh[++oldSIdx];
        } else if (oldEnode == null) {
            oldEnode = oldCh[--oldEIdx];
        } else if (newStnode == null) {
            newStnode = newCh[++newSIdx];
        } else if (newEnode == null) {
            newEnode = newCh[--newEIdx];
        } else if (same(oldSnode, newStnode)){
            oldSnode = oldCh[++oldSIdx];
            newStnode = newCh[++newSIdx];
        } else if (same(oldEnode, newEnode)) {
            oldEnode = oldCh[--oldEIdx];
            newEnode = newCh[--newEIdx];
        }else if (same(oldSnode, newEnode)) {
            insertBerfore(parentElm,'old-'+oldSnode,oldCh[oldEIdx+1],'left');
            oldSnode = oldCh[++oldSIdx];
            newEnode = newCh[--newEIdx];
        }else if (same(oldEnode, newStnode)) {
            insertBerfore(parentElm,'old-'+oldEnode,oldCh[oldSIdx],'right');
            oldEnode = oldCh[--oldEIdx];
            newStnode = newCh[++newSIdx];
        } else {
            insertBerfore(parentElm,'new-'+newStnode,oldCh[oldSIdx],'diff');
            newStnode = newCh[++newSIdx];
        }
        console.log('------------------------------------------------------------------')
        console.log('第'+ (++conunt) + '次对比,oldSIdx:'+oldSIdx + ' oldEIdx:' +oldEIdx + ' newSIdx:'+newSIdx+ ' newEIdx:'+newEIdx )
        console.log(oldCh.slice(oldSIdx,oldEIdx+1))
        console.log(newCh.slice(newSIdx,newEIdx+1))
        console.log(parentElm);
    }
    // 最后比较完成之后
    if (oldSIdx <= oldEIdx || newSIdx <= newEIdx) {
        console.log('Diff 对比结束')
        console.log(oldCh)
        console.log(newCh)
        if (oldSIdx > oldEIdx) {
            // 'old-'用来模拟区分新旧节点
            console.log('新增节点')
            let before =newCh[newEIdx+1] == null ? null : 'old-'+ newCh[newEIdx+1];
            addVnodes(parentElm, before, newCh, newSIdx, newEIdx);
        } else {
            console.log('移除节点')
            removeVnodes(parentElm, oldCh, oldSIdx, oldEIdx);
        }
        console.log('模拟DOM更新完成')
        console.log(parentElm);
    }
}

4.0 附件

Snabbdom 源代码地址：https://github.com/snabbdom/snabbdom

Snabbdom 底层Diff算法详解

前言

1.0 Snabbdom Diff 方式

2.0 Snabbdom Diff 过程

3.0 代码模拟过程

4.0 附件