Vue2.0的Diff算法

Vue2.0加入了Virtual Dom，Vue的Diff位于patch.js文件中，该算法来源于snabbdom，复杂度为O(n)

React的 Diff其实和Vue的 Diff 大同小异，只比较同层级节点，不会跨层级比较，目的就是最小变动

Diff 的过程就是调用 patch 函数，就像打补丁一样修改真实DOM。

patch函数

// 只保留核心部分
function patch(oldVnode, vnode) {
    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode)
    } else {
        const oEl = oldVnode.el
        let parentEle = api.parentNode(oEl)
        createEle(vnode)
        if (parentEle !== null) {
            api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
            api.removeChild(parentEle, oldVnode.el)
            oldVnode = null
        }
    }
    return vnode
}

(oldVnode, vnode) 也就是新旧两个虚拟DOM节点，一个完整的 vnode 都有什么属性：

// body下的 <div id="v" class="classA"><div> 对应的 oldVnode 就是
{
  el:  div  // 对真实节点的引用，document.querySelector('#id.classA')
  tagName: 'DIV',   // 节点的标签
  sel: 'div#v.classA'  // 节点的选择器
  data: null,   // 一个存储节点属性的对象，对应节点的 el[prop] 属性，如onclick, style
  children: [],  // 存储子节点的数组，每个子节点也是 vnode 结构
  text: null,    // 如果是文本节点，对应文本节点的textContent，否则为null
}

需要注意的是，属性 el 引用的是此 Virtual DOM对应的真实DOM，patch() 的参数 vnode 中的 el 最初为 null，因为 patch() 之前它还没有对应的真实DOM

patch(oldVnode, vnode) 的第一部分：

    if (sameVnode(oldVnode, vnode)) {
        patchVnode(oldVnode, vnode)
    }

sameVnode() 的作用是看这两个节点是否值得比较，代码很简单：

    function sameVnode(oldVnode, vnode){
        // 只保留核心部分
        return vnode.key === oldVnode.key && vnode.sel === oldVnode.sel
    }

两个 vnode 的 key 和 sel 相同才会去比较它们，比如 p和span、div.classA和div.classB 都被认为是不同结构而不去比较它们。
不值得比较的节点会进入 else 中，过程如下：

else {
    // 1. 获取 oldVnode.el 的父节点，parentEle 是真实DOM
    const oEl = oldVnode.el
    let parentEle = api.parentNode(oEl)
    // 2. 为 vnode 创建它的真实DOM，令 vnode.el = 真实DOM
    createEle(vnode)
    if (parentEle !== null) {
        // 3. parentEle 将新的DOM插入，移除旧的DOM
        api.insertBefore(parentEle, vnode.el, api.nextSibling(oEl))
        api.removeChild(parentEle, oldVnode.el)
        oldVnode = null
    }
}

当不值得比较时，新节点直接把老节点整个替换掉了
最后执行：return vnode，返回的 vnode 与传入时的 vnode 的区别就在于：vnode.el，之前 vnode.el=null，而现在 vnode.el=对应的真实DOM

    var oldVnode = patch (oldVnode, vnode)

至此完成一个patch过程。

patchVnode(oldVnode, vnode)
两个节点值得比较时，会调用 patchVnode() 函数

patchVnode (oldVnode, vnode) {
    // 只保留核心部分
    const el = vnode.el = oldVnode.el    // 引用真实DOM
    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)
        }
    }
}

const el = vnode.el = oldVnode.el 这是很重要的一步，让 vnode.el 引用到当前的真实DOM，当 el 变量修改时，vnode.el 会同步变化。
节点比较的5种情况

if (oldVnode === vnode) 它们的引用一致，可以认为没有变化，直接return
if (oldVnode.text !== null && vnode.text !== null && oldVnode.text !== vnode.text) 文本节点的比较，需要修改时，则会调用 oldVnode.textContent = vnode.text
if (oldCh && ch && oldCh !== ch) 两个节点都有子节点，且它们不一样，则调用 updateChildren() 函数去比较子节点，这是Diff的核心
else if (ch) 只有新的节点有子节点，调用 createEle(vnode)，vnode.el 已经引用了老的DOM几点，createEle函数会在老的DOM节点上添加子节点。
else if (oldCh) 新节点没有子节点，老节点有子节点，则直接删除老节点。

updateChildren

function 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
    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)) {  // 比较方式一
            // 头头比较通过，patch不同之处，如class、style
            patchVnode(oldStartVnode, newStartVnode)
            // 向后移动指针
            oldStartVnode = oldCh[++oldStartIdx]
            newStartVnode = newCh[++newStartIdx]
        } else if (sameVnode(oldEndVnode, newEndVnode)) {  // 比较方式二
            // 尾尾比较通过，patch不同之处
            patchVnode(oldEndVnode, newEndVnode)
            // 向前移动指针
            oldEndVnode = oldCh[--oldEndIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldStartVnode, newEndVnode)) {  // 比较方式三
            // 旧头与新尾比较通过，patch不同之处
            patchVnode(oldStartVnode, newEndVnode)
            // 移除这个旧节点，再添加到数组尾部
            api.insertBefore(parentElm, oldStartVnode.el, api.nextSibling(oldEndVnode.el))
            oldStartVnode = oldCh[++oldStartIdx]
            newEndVnode = newCh[--newEndIdx]
        } else if (sameVnode(oldEndVnode, newStartVnode)) {  // 比较方式四
            // 新头与旧尾比较通过，patch不同之处
            patchVnode(oldEndVnode, newStartVnode)
            // 移除这个旧节点，再添加到数组头部
            api.insertBefore(parentElm, oldEndVnode.el, oldStartVnode.el)
            oldEndVnode = oldCh[--oldEndIdx]
            newStartVnode = newCh[++newStartIdx]
        } else {
            // 四种比较方式都不满足，如果设置了key，则使用 key 比较
            if (oldKeyToIdx === undefined) {
                // 由key生成index表，由此可见，应该给节点数组设置唯一key
                oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
            }
            idxInOld = oldKeyToIdx[newStartVnode.key]
            if (!idxInOld) {
                // 用新节点的key在 旧节点数组中查找，没有找到这个节点，则插入新节点
                api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                newStartVnode = newCh[++newStartIdx]
            } else {
                elmToMove = oldCh[idxInOld]
                if (elmToMove.sel !== newStartVnode.sel) {
                    // key虽相同，但节点不同，把这个旧节点替换成新节点
                    api.insertBefore(parentElm, createEle(newStartVnode).el, oldStartVnode.el)
                } else {
                    // 两个节点相同，则patch不同之处
                    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)
    }
}

代码很密集，用图描述这个过程：

updateChildren.png

只有在 oldCh和newCh 都存在的情况下才会执行updateChildren()，可知updateChildren()进行的是同层级下的Children的更新比较，也就是传说中的Diff了。

一系列变量

旧节点数组oldCh，新节点数组newCh
oldStartIdx、oldEndIdx 分别指向oldCh头部和尾部，对应元素oldStartVnode、oldEndVnode
newStartIdx、newEndIdx 分别指向newCh头部和尾部，对应元素newStartVnode、newEndVnode
oldKeyToIdx 是一个Map，其key就是v-bind:key的值，value对应的就是当前vnode

过程可以概况为：
头头比较、尾尾比较，头尾比较，尾头比较，如果 4 种比较都不匹配，但设置了key，则会用key进行比较。

具体的Diff分析

Vue2在比较过程中会直接操作DOM，相比之下，React把Diff和DOM操作分为两个阶段，DOM操作在提交阶段。
Diff的遍历过程中，只要是对DOM的操作都会调用 api.insertBefore()，api.insertBefore()只是原生insertBefore()的简单封装。

官方文档：parentElement.insertBefore(newElement, referenceElement)，如果referenceElement为null，则newElement将被插入到子节点的末尾；如果newElement已经存在于DOM树中，则首先会从DOM树中移除。

对于头头比较sameVnode(oldStartVnode, newStartVnode)和尾尾比较sameVnode(oldEndVnode, newEndVnode) ，为true时是不需要对移动DOM的，只是更新节点(patchVnode)。
设置 key (v-bind:key="xxx") 与不设置 key 的区别：
- 不设key(undefined)，newCh和oldCh只会进行头尾两端的相互比较；而且 sameVnode() 在判断两个节点是否值得比较时，无法比较key是否相同。
  在特定情况下，比如v-for的列表是10个多选框，选中哪一个则删除哪一个，那么会发现：删除第一个checkbox，新的第一个checkbox会处于选中状态！
- 设置key，如果头尾两端的比较都不匹配，还会从用 key 生成的Map对象 oldKeyToIdx 中查找匹配的节点，最大化的复用节点，提高性能。
- 不建议直接用 index 作为 key，其实就相当于不加key。当删除/插入元素时，因为后续元素的key="index"都会发生变化，导致它们重新渲染，无法复用，浪费性能。
  key="index"只适用于比较稳定的状态。
当sameVnode(oldStartVnode, newEndVnode) 值得比较时，说明 oldStartVnode.el 跑到 oldEndVnode.el 的后边了。

假设startIdx遍历到1.png

当 sameVnode(oldEndVnode, newStartVnode) 值得比较，oldEndVnode.el 跑到了 oldStartVnode.el 的前边。
准确的说应该是 oldEndVnode.el 需要移动到 oldStartVnode.el的前边。
而实际操作是，先插入，后移除。

2038.png

4种头尾方式比较完后，就会去检查旧节点的Map表。根据新节点的key，到表中查找是否有这样一个节点。
- 找不到，说明这个新节点不存在与旧节点树中，将新节点插入到 oldStartVnode.el 的前边。

createEle.png

找到了，也要去检查两个节点是否还是同一节点elmToMove.sel !== newStartVnode.sel
如果是同一节点，则更新节点，移动到新的位置；否则，替换这个旧节点。

while循环结束后（新、旧有一个发生了交叉），也分为两种情况：
- oldStartIdx > oldEndIdx 表示旧节点先遍历完。当然有可能 newCh 也刚好遍历完，但都归为此类。
  那么，直接插入剩下的新节点即可。

before.png

newStartIdx > newEndIdx 表示新节点遍历结束，那么就移除剩下的旧节点。

remove.png

小结

尽量不要跨层级的修改DOM
设置 Key 可以最大化的利用节点
不要盲目相信 Diff 的效率，在必要时可以手工优化

举个例子.png

原有的 oldCh 的顺序是 A 、B、C、D、E、F、G，更新后成 ch 的顺序 F、D、A、H、E、C、B、G

初始状态.png

为了更好理解后续的 STEP，先看下相关符合标记的说明：

图解说明.png

STEP-1
对比 A-F --> G-G，sameVnode(oldEndVnode, newEndVnode)值得比较，DOM顺序不变

对 G 进行patchVnode()，更新oldG.el
移动指针：--oldEndIdx，--newEndIdx

step-1.png

STEP-2
对比 A-F --> F-B --> A-B --> F-F，sameVnode(oldEndVnode, newStartVnode)值得比较

对 F 进行patchVnode()，更新oldF.el
找到 oldStartVnode 在DOM中的位置A，在其前面插入更新后的F
移动指针：--oldEndIdx，++newStartIdx

step-2.png

STEP-3
对比 A-D --> E-B --> A-B --> E-D，sameVnode(old, new)都不匹配，则取newStartVnode的key，即D.key，在 oldKeyToIdx 中查找，并成功找到对应的D

将 D 赋值给 elmToMove，图示中为vnodeToMove
对 D 进行patchVnode()，更新oldD.el
将 oldCh 中对应D的vnode置空：oldCh[idxInOld] = null
找到 oldStartVnode 在DOM中的位置A，在其前面插入更新后的D
移动指针：++newStartIdx

step-3.png

STEP-4
对比 A-A，sameVnode(oldStartVnode, newStartVnode)匹配成功，进行比较，DOM顺序不变

将 A 进行patchVnode()，更新oldA.el
移动指针：++oldStartIdx，++newStartIdx

step-4.png

STEP-5
对比 B-H --> E-B --> B-B，sameVnode(oldStartVnode, newEndVnode)值得比较

将 B 进行patchVnode()，更新oldB.el
找到 oldEndVnode - E 的下一个兄弟节点 G，在其前面（G前面、E后面）插入更新后的B
移动指针：++oldStartIdx，--newEndIdx

step-5.png

STEP-6
对比 C-H --> E-C --> C-C，sameVnode(oldStartVnode, newEndVnode)值得比较（同STEP-5）

将 C 进行patchVnode()，更新oldC.el
找到 oldEndVnode - E 的下一个兄弟节点 B，在其前面（B前面、E后面）插入更新后的C
移动指针：++oldStartIdx，--newEndIdx

step-6.png

STEP-7
因为 STEP-3 中的 oldCh[idxInOld] = null，当前获取的 oldStartVnode = null

移动指针：++oldStartIdx

step-7.png

STEP-8
对比 E-H --> E-E，sameVnode(oldEndVnode, newEndVnode)值得比较，DOM顺序不变

将 E 进行patchVnode()，更新oldE.el
移动指针：--oldEndIdx，--newEndIdx

step-8.png

last
此时的 oldStartIdx > oldEndIdx，有一方发生了交叉，则退出循环。

        if (oldStartIdx > oldEndIdx) {
            before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].el
            addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx)
        }

旧VirtualDOM 首先发生交叉，所以把新VirtualDOM中剩余的节点直接插入到oldCh中

找到 newEndIdx + 1 位置E --> before
剩余的待处理部分：newStartIdx -- newEndIdx 之间的 vnode 视为新增的部分 -- [ H ]
插入到 before 位置E 的前面

last.png

注意点

在Diff过程中，oldCh 和 newCh 的位置并不会发生变化，真正进行操作的是传入的parentElm -- 父vnode的elm
插入操作使用的 insertBefore(newElement, referenceElement)，在指定节点前插入。
patch() 中其实还有一个数组insertedVnodeQueue，涉及到组件的patch过程：组件的 $mount 函数之后之后并不会立即触发组件实例的mounted钩子，而是把当前实例push到insertedVnodeQueue中，然后在patch的倒数第二行执行invokeInsertHook -- 触发所有组件实例的insert钩子，而组件的insert钩子函数中才会触发组件实例的mounted钩子。比如，在patch的过程中，patch了多个组件vnode，它们都进行了$mount即生成DOM，但没有立即触发mounted，而是等整个patch完成，再逐一触发。