virtualDom的DIFF算法关键过程整理

摘要：，文本节点的比较，需要修改，则会调用。两个节点都有子节点，而且它们不一样，这样我们会调用函数比较子节点，这是的核心。，新节点没有子节点，老节点有子节点，直接删除老节点。参考文章解析的算法

function sameVnode(oldVnode, vnode){
    return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
}

如果值得比较会执行patchVnode(oldVnode, vnode)

如果不值得比较，新节点直接把老节点整个替换了

patchVnode (oldVnode, vnode) {
    const el = vnode.el = oldVnode.el
    let i, oldCh = oldVnode.children, ch = vnode.children
    if (oldVnode === vnode) return
    if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) {
        api.setTextContent(el, vnode.text)
    }else {
        updateEle(el, vnode, oldVnode)
        if (oldCh && ch && oldCh !== ch) {
            updateChildren(el, oldCh, ch)
        }else if (ch){
            createEle(vnode) //create el"s children dom
        }else if (oldCh){
            api.removeChildren(el)
        }
    }
}

节点的比较有5种情况

if (oldVnode === vnode)，他们的引用一致，可以认为没有变化。

if(oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text)，文本节点的比较，需要修改，则会调用Node.textContent = vnode.text。

if( oldCh && ch && oldCh !== ch ), 两个节点都有子节点，而且它们不一样，这样我们会调用updateChildren函数比较子节点，这是diff的核心。

else if (ch)，只有新的节点有子节点，调用createEle(vnode)，vnode.el已经引用了老的dom节点，createEle函数会在老dom节点上添加子节点。

else if (oldCh)，新节点没有子节点，老节点有子节点，直接删除老节点。

updateChildren (parentElm, oldCh, newCh) {
    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
    let idxInOld
    let elmToMove
    let before
    while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
            if (oldStartVnode == null) {   //对于vnode.key的比较，会把oldVnode = null
                oldStartVnode = oldCh[++oldStartIdx] 
            }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)
                oldStartVnode = oldCh[++oldStartIdx]
                newStartVnode = newCh[++newStartIdx]
            }else if (sameVnode(oldEndVnode, newEndVnode)) {
                patchVnode(oldEndVnode, newEndVnode)
                oldEndVnode = oldCh[--oldEndIdx]
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldStartVnode, newEndVnode)) {
                patchVnode(oldStartVnode, newEndVnode)
                api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
                oldStartVnode = oldCh[++oldStartIdx]
                newEndVnode = newCh[--newEndIdx]
            }else if (sameVnode(oldEndVnode, newStartVnode)) {
                patchVnode(oldEndVnode, newStartVnode)
                api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
                oldEndVnode = oldCh[--oldEndIdx]
                newStartVnode = newCh[++newStartIdx]
            }else {
               // 使用key时的比较
                if (oldKeyToIdx === undefined) {
                    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx) // 有key生成index表
                }
                idxInOld = oldKeyToIdx[newStartVnode.key]
                if (!idxInOld) {
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    newStartVnode = newCh[++newStartIdx]
                }
                else {
                    elmToMove = oldCh[idxInOld]
                    if (elmToMove.sel !== newStartVnode.sel) {
                        api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                    }else {
                        patchVnode(elmToMove, newStartVnode)
                        oldCh[idxInOld] = null
                        api.insertBefore(parentElm, elmToMove.el, oldStartVnode.el)
                    }
                    newStartVnode = newCh[++newStartIdx]
                }
            }
        }
        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
        }else if (newStartIdx > newEndIdx) {
            removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
        }
}

主要的思路大概就是，定义变量，分别记录当前比较的新、旧节点中的首尾索引与节点（oldStartVnode、oldEndVnode、newStartVnode、newEndVnode）（后续称为比较区间）

(图片来自：https://github.com/aooy/blog/... )

通过对 oldStartVnode、oldEndVnode、newStartVnode、newEndVnode 做,两两的 sameVnode 比较

比较判断有4种，按顺序依次比较
oldStartVnode —— newStartVnode （头对头）
oldEndVnode —— newEndVnode （尾对尾）
oldStartVnode —— newEndVnode （头对尾）
oldEndVnode —— newStartVnode （尾对头）

如果其中一种比较成立了，那么oldVode中的相应节点会 以当前比较区间为基准 移到newVnode相应的位置上，
然后比较区间会根据当前的比较条件类型，以头或尾为缩小比较区间的方向，缩小区间

例如： 当oldStartVnode，newEndVnode值得比较时, 将oldStartVnode.el移动到oldEndVnode.el后边

当4种比较都不成立时，会使用key去比较，并在最终都使newVode的比较区间，头部 减1

当oldVnode的key列表中能匹配到对应的key时，判断比较节点的选择器属性是否一样

不一样则直接在当前比较区间的头部,新创建一个newVnode的Dom插入

比较节点中的oldVnode无需处理，因为后面的比较中不会有成立的比较条件，最终会直接删除节点

如果一样则将比较节点中的oldVnode移动到当前比较区间的头部（所以为节点设置key可以更高效的利用dom），并将比较区间中oldVnode原本的索引位置赋值为Null

如果最终key列表也没能匹配到的话，也是直接在当前比较区间的头部,新创建一个newVnode的Dom插入。

最后在结束时会存在2种情况

oldStartIdx > oldEndIdx

oldVnode先遍历完，证明newVode有新增的节点，或者一致，这种情况会将newVode剩余的节点插入到oldVnode比较区间的末尾

newStartIdx > newEndIdx

这时是newVode先遍历完，证明newVode里删除了某些节点，此时oldVnode的比较区间节点是已经不存在的，会将他们删除。

参考文章：解析vue2.0的diff算法