Picodom中的diff算法补完

内容简介：Picodom中的diff算法补完

上次看 Picodom 代码的时候，patch 函数中有段代码没怎么看懂，所以就没分析，算是挖下了坑。经过这几天的思考，我终于把逻辑想明白了，今儿咱就来把这个坑给填上~（美错儿，我今天又要划水了，来打我呀打我呀打我呀~）

逻辑梳理

上次看到 Picodom 中的 patch 函数中，逻辑分为三个分支，分别是新增节点（没有oldNode），修改节点（newNode和oldNode标签名一样），替换节点（newNode和oldNode标签名不一样）。其中，新增节点和替换节点的操作比较简单。单修改节点的操作，除了要修改节点本身的属性外，还要对比更新节点的子节点，逻辑比较复杂，直接讲代码的话不太容易看出其中的逻辑，咱们先来梳理一下。

说到子节点变化，一般会分为以下这几种情况：

增加新节点：有可能在旧列表的最开始，中间或者之后添加
复用旧节点：还记得之前看的代码中，Picodom 会把节点的 key 属性特殊对待吗？这里就是把 key 作为节点的唯一标识的，只要 key 对上了就认为是能复用，dom节点不用新建，不过位置有可能发生变化
删除旧节点：删除单个或者多个节点
把以上这些情况综合起来~

如图，比如像下面这种情况：

Picodom中的diff算法补完

其实这逻辑说起来感觉还挺简单，但是如何用代码实现呢？我们先说下 Picodom 的处理方法，以上图为例。

遍历新节点列表，新节点列表和旧节点列表里各取一个，作为当前新节点和当前旧节点，对比他们，这俩节点 key 不一样，而且在旧节点列表里也没有找到这个节点，于是在当前旧节点前添加新节点，当前新节点切换到下一节点。

Picodom中的diff算法补完

当前新节点和当前旧节点 key 不一样，但是在旧节点列表里能找到，就把找到的旧节点插入到当前旧节点前面，当前新节点切换到下一节点。

Picodom中的diff算法补完

对新节点列表中的 4 和 7 的处理和前面一样，就不再多说了。处理过他们之后，取到的当前新节点和当前旧节点的 key 是一样的。这时把新旧节点都传入 patch 函数，递归处理这两个节点。处理过之后，当前新节点和当前旧节点都切换到下一节点。

Picodom中的diff算法补完

根据之前的步骤，把 2 也处理了，最后当前新节点是 8 ，当前旧节点是 3 ，8 是新增的，所以插入到 3 前面。

Picodom中的diff算法补完

最后将未用到的旧节点删除掉，既把 3 删掉，得到最终结果。

实现

ok，让我们来看下 Picodom 是如何用代码来实现上述逻辑的：

// ...

var len = node.children.length
// 新子节点vnode列表的长度
var oldLen = oldNode.children.length
// 旧子节点vnode列表的长度
var reusableChildren = {}
// 可复用节点列表
var oldElements = []
// 旧子节点dom列表
var newKeys = {}
// 这边变量用来标记新子节点列表中复用的节点

for (var i = 0; i < oldLen; i++) {
    var oldElement = element.childNodes[i]
    oldElements[i] = oldElement

    var oldChild = oldNode.children[i]
    var oldKey = getKeyFrom(oldChild)

    if (null != oldKey) {
        reusableChildren[oldKey] = [oldElement, oldChil]
    }
}
// 上面这个循环是在遍历旧子节点vnode列表，把有key的挑出来，放到可复用节点列表里

var i = 0
var j = 0
// i是旧子节点vnode列表的索引，j是新子节点vnode列表的索引

while (j < len) {
// 遍历新子节点vnode列表
    var oldElement = oldElements[i]
    // 取当前旧节点dom
    var oldChild = oldNode.children[i]
    // 取当前旧节点vnode
    var newChild = node.children[j]
    // 取当前新节点vnode

    var oldKey = getKeyFrom(oldChild)
    // 取当前旧节点的key
    
    if (newKeys[oldKey]) {
        i++
        continue
    }
    // 上面这个判断是为了跳过已经被使用过的旧子节点

    var newKey = getKeyFrom(newChild)
    // 取当前新节点的key

    var reusableChild = reusableChildren[newKey] || []
    // 取当前新节点key对应的可复用节点
    if (null == newKey) {
        if (null == oldKey) {
            patch(element, oldElement, oldChild, newChild)
            j++
            // 如果新节点和旧节点都没有key则在当前旧节点对应的dom节点前插入新节点
            // 然后切换当前新节点
        }
        i++
        // 这里的处理方式让人很难理解，为啥是新节点和旧节点都没有key的时候才插入？
        // 我感觉这样处理主要是为了处理文本节点……因为文本节点是肯定没有key的
        // 另外如果新节点里出现了一个没有key的节点，
        // 那么上面这段逻辑就会一直切换的当前旧节点，
        // 直到找到一个同样没有key的旧节点，再用patch对比两个节点，
        // 如果一直没有找到没有key的旧节点，最后oldElement和oldChild都是null，
        // 相当于在旧节点列表最后添加一个新的节点，
        // 此时当前旧节点已经切到旧节点列表最后了，
        // 所以后续的所有操作都是往旧节点列表最后添加新的节点
    } else {
        if (oldKey === newKey) {
            patch(element, reusableChild[0], reusableChild[1], newChild)
            i++
            // 如果新节点和旧节点的key相同，则用patch再去对比这两个节点
        } else if (reusableChild[0]) {
            element.insertBefore(reusableChild[0], oldElement)
            patch(element, reusableChild[0], reusableChild[1], newChild)
            // 如果key不相同但是存在可复用节点，则把可复用节点插入到当前旧节点前面
        } else {
            patch(element, oldElement, null, newChild)
            // 如果key不同而且不存在可复用节点，则在当前旧节点前面插入个新节点
        }

        j++
        // 切换当前新节点
        newKeys[newKey] = newChild
        // 记录已经使用的节点的key，后续可以用来过滤出已经使用的可复用节点
    }
}
// 根据key复用旧节点

while (i < oldLen) {
    var oldChild = oldNode.children[i]
    var oldKey = getKeyFrom(oldChild)
    if (null == oldKey) {
        removeElement(element, oldElements[i], oldChild)
    }
    i++
}
// 移除没有key的旧节点

for (var i in reusableChildren) {
    var reusableChild = reusableChildren[i]
    var reusableNode = reusableChild[1]
    if (!newKeys[reusableNode.data.key]) {
        removeElement(element, reusableChild[0], reusableNode)
    }
}
// 根据新节点的key过滤并移除掉已经使用的可复用节点

// ...

思考

看过代码之后我们会发现，如果出现没有key的节点那么之前那套算法的效率就会变差，因为有可能需要遍历整个旧节点列表之后才能对比，这也就是不难理解为啥之前版本的react会自动生成一个datareact-id了……从这个角度来看，感觉给节点加上唯一key做表示可以提升界面更新的效率，不知道react或者vue里这么搞是不是有效……

Picodom中的diff算法补完