关于vue.js:Vue源码解读二虚拟DOM与Diff算法

什么是虚构 DOM？

virtual DOM，用一般 js 对象来形容 DOM 构造，因为不是实在 DOM，所以称之为虚构 DOM。

虚构 DOM 在 Vue 中的利用
Vue 的编译器在编译模板之后，会把这些模板编译成一个渲染函数。而函数被调用的时候就会渲染并且返回一个虚构 DOM 的树。Vue 的 Virtual DOM Patching 算法是基于 Snabbdom 的实现。
当咱们有了这个虚构的树之后，再交给一个 Patch 函数，负责把这些虚构 DOM 真正施加到实在的 DOM 上。在这个过程中，Vue 有本身的响应式零碎来侦测在渲染过程中所依赖到的数据起源。在渲染过程中，侦测到数据起源之后就能够准确感知数据源的变动。到时候就能够依据须要从新进行渲染。当从新进行渲染之后，会生成一个新的树，将新的树与旧的树进行比照，就能够最终得出应施加到实在 DOM 上的改变。最初再通过 Patch 函数施加改变。
简略点讲，在 Vue 的底层实现上，Vue 将模板编译成虚构 DOM 渲染函数。联合 Vue 自带的响应零碎，在应该状态扭转时，Vue 可能智能地计算出从新渲染组件的最小代价并应到 DOM 操作上。
Snabbdom 虚构 DOM 实现思路解读

以此 html 页面内容为例

body>
    <button id="btn"> 点击我扭转 </button>
    <div id="container"></div>
    <script src="/xuni/bundle.js"></script>
</body>

const container = document.getElementById('container');
const btn = document.getElementById('btn')
const myVnode1 = h('ul', {}, [h('li', {key: 'A'}, 'A'),
    h('li', {key: 'B'}, 'B'),
    h('li', {key: 'C'}, 'C'),
    h('li', {key: 'D'}, 'D'),
    h('li', {key: 'E'}, 'E')
]);
patch(container, myVnode1)

解读 h 函数
h 函数就是 vue 中的 createElement 办法，它是用来创立虚构 DOM，追踪 DOM 变动，最终返回虚构 DOM, 即 js 封装好的节点对象。
h 函数的简略剖析如下：

/**  低配版本的 h 函数，这个函数必须接管 3 个参数，缺一不可
 相当于它的重载性能较弱
 也就是说，调用的时候状态必须是以下三种之一：状态①：h('div', {}, '文字')
 状态二：h('div', {}, [])
 状态三：h('div', {}, h())
*/
export default function(sel, data, c) {
 // 查看参数的个数
 if (arguments.length !== 3) {throw new Error('h 函数必须传入 3 个参数，低配版 h 函数');
 }
 // 查看参数 c 的类型
 if (typeof c === 'string' || typeof c === 'number') {
     // 阐明当初调用 h 函数就是状态①
     return vnode(sel, data, undefined, c, undefined);
 } else if (Array.isArray(c)) {
     // 阐明当初调用 H 函数就是状态②
     let children = []
     // 遍历 c，收集 children
     for (let i = 0; i < c.length; i++) {// c[i] 必须是一个对象，如果不满足
         if (!(typeof c[i] === 'object' && c[i].hasOwnProperty('sel'))) {throw new Error('传入的数组参数中有项不是 h 函数')
         }
         // 这里不必执行 c[i]，因为测试语句中曾经调用了，既是执行 h 函数了
         // 此时只须要收集好就能够了
         children.push(c[i])
     }
     return vnode(sel, data,children, undefined, undefined)
 } else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
     // 阐明是调用 h 函数状态③
     // 即传入的 c 是惟一的孩子，间接存入 children
     let children = ;
     return vnode(sel, data, children, undefined, undefined)
 } else {throw new Error('传入的第三个参数类型不对')
 }
}

vNode 函数就是用来标准 h 中传入的参数，将传入的参数 data 中的属性 key 提出来，作为返回值对象中的一个属性，返回整合之后的对象

// 函数的性能非常简单，就是把传入的 5 个参数组合成对象再返回
export default function(sel, data, children, text, elm) {
 const key = data.key;
 return {sel, data, children, text, elm, key}
}

调用 h 函数后失去的 myVnode1 打印如下图：

解读 patch 函数
也就是 patch 算法，在 patch 函数中传入新旧两个节点，比拟两者的不同，如雷同，则进一步进行 精细化比拟 ，否则，在 老节点之前插入新节点，并且删除旧节点，这个过程也是将虚构 DOM 渲染到实在 DOM 中，最终视图更新。

``patch.js
export default function (oldVnode, newVnode) {
    // 判断传入的第一个参数，是 dom 节点还是虚构节点
    if (oldVnode.sel === '' || oldVnode.sel == undefined) {
        // 传入的第一个参数是 dom 节点，此时要包装为虚构节点
        oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode)
    }
    // console.log(oldVnode)

    // 判断 oldv 和 newv 是不是同一个节点
    if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {
        // 是则进行精细化比拟
        patchVnode(oldVnode, newVnode)
    } else {
        // 不是，则暴力插入新的，删除旧的
        // console.log('新老节点不是一个，则暴力插入新的，删除旧的')
        // 插入地位：老节点之前
        let newVnodeElm = createElement(newVnode)
        // 插入到老节点之前
        if (oldVnode.elm.parentNode && newVnodeElm) {oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
        }
        // 删除旧的节点
        oldVnode.elm.parentNode.removeChild(oldVnode.elm)
    }
}

其中 createElement 函数就是将虚构 dom 转换为真正 dom 的解决办法。

/** 真正创立节点, 将 vnode 创立为 dom, 插入到 pivot 之前
*/
export default function createElement (vnode) {// console.log('目标是把虚构节点', vnode, '真正变为 dom');
    let domNode = document.createElement(vnode.sel);
    // 有子节点还是文本
    // 创立一个节点，这个节点当初还是孤儿节点
    if (vnode.text != '' && (vnode.children == undefined || vnode.children.length === 0)) {
        // 它外部是文字
        domNode.innerText = vnode.text

    } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
        // 它外部是子节点，须要递归创立节点
        for (let i = 0; i < vnode.children.length; i++) {
            // 失去以后这个 children
            let ch = vnode.children[i];
            // console.log(ch)
            // 创立出它的 dom，一旦调用 createElement 意味着：创立出 DOM 了，并且它的 elm 属性指向了创立出的 DOM，然而还没有上树，是一个孤儿节点
            let chDOM = createElement(ch)
            domNode.appendChild(chDOM)
        }
        // vnode.elm = domNode
    }
    // 补充 elm 属性
    vnode.elm = domNode
    // 返回 elm，elm 是一个纯 dom
    return vnode.elm;
}

调用 createElement 函数之后生成真正的 dom，最初 dom 节点通过 insertBefore 办法指定到旧节点之前上树。

精细化比拟 - 解读 patchVnode 函数
此种状况的前提是新旧节点都存在，且新旧节点惟一标识 key 雷同，标签名 sel 雷同。
patchVnode 函数中次要比拟新旧虚构节点中是否有 text 属性，是否有子节点 children
1)若新节点中有 text，与旧节点相比拟，若不同，间接替换；即便旧节点没有 text 而是有 children，也间接替换，若雷同不做解决；
2)若新节点中有子节点 children，此时须要判断旧节点有无子节点 children，若旧节点也有子节点，则须要更进一步 子节点更新策略 updateChildren，若旧节点没有子节点，则清空老节点的内容，遍历新的子节点，创立 dom, 上树

// 比照同一个虚构节点
export default function patchVnode (oldVnode, newVnode) {
    // 判断新旧 vnode 是否是同一个对象
    if (oldVnode === newVnode) return;
    // 判断新 vnode 没有没 text 属性
    if (newVnode.text != undefined && (newVnode.children == undefined || newVnode.children.length === 0)) {console.log('新 vnode 有 text 属性')
        if (newVnode.text !== oldVnode.text) {
            // 如果新虚构节点中的 text 和老的虚构节点 text 不同，那么间接让新的 text 写入老的 elm 中即可，如果老的 elm 中是 children，那么也会立刻隐没
            oldVnode.elm.innerText = newVnode.text
        }
    } else {
        // 新 vnode 没有 text 属性，有 children
        console.log('新 vnode 没有 text 属性')
        if (oldVnode.children != undefined && oldVnode.children.length > 0) {
            // 老的有 children，新的也有 children，就是最简单的状况，就是新老都有 children
            updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
        } else {console.log('oldVnode', oldVnode)
            // 老的没有 children，新的有 children
            updateChildren(oldVnode.elm, oldVnode.children, newVnode.children)
            // 清空老的节点的内容
            oldVnode.elm.innerHtml = '';
            // 遍历新的 vnode 的子节点，创立 dom, 上树
            for (let i = 0; i < newVnode.children.length; i++) {let dom = createElement(newVnode.children[i]);
                oldVnode.elm.appendChild(dom)
            }
        }
    }
}

子节点更新测试 updateChildren 函数解读
上一步中提到的新老节点都有子节点时，则须要进一步的子节点比拟，大体来说就是更新节点，新增节点，删除节点，挪动节点，这个函数中利用旧节点开始标记，完结标记，新节点开始标记，完结标记四个指针地位的挪动进行指针所指地位上的元素比拟来解决什么状况下更新节点，什么状况下新增节点。

export default function updateChildren (parentElm, oldCh, newCh) {console.log('我是 updateChildren,oldCh', oldCh)
 console.log('newCh', newCh)
 // 旧前
 let oldStartIdx = 0;
 // 新前
 let newStartIdx = 0;
 // 旧后
 let oldEndIdx = oldCh.length - 1;
 // 新后
 let newEndIdx = newCh.length - 1;
 // 旧前节点
 let oldStartVnode = oldCh[0];
 // 旧后节点
 let oldEndVnode = oldCh[oldEndIdx];
 // 新前节点
 let newStartVnode = newCh[0];
 // 新后节点
 let newEndVnode = newCh[newEndIdx];
 // 
 let keyMap = null;
 // 开始大 while 了
 while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
     // 首先不是判断①②③④命中，而是要略过曾经加 undefined 标记的货色
     if (oldStartVnode == null || oldCh[oldStartIdx] == undefined) {oldStartVnode = oldCh[++oldStartIdx];
     } else if (oldEndVnode == null || oldCh[oldEndIdx] == undefined) {oldEndVnode = oldCh[--oldEndIdx];
     } else if (newStartVnode == null || newCh[newStartIdx] == undefined) {newStartVnode = newCh[++newStartIdx];
     } else if (newEndVnode == null || newCh[newEndIdx] == undefined) {newEndVnode = newCh[--newEndIdx];
     } else if (checkSameVnode(oldStartVnode, newStartVnode)) {
         // 新前和旧前
         console.log('①新前和旧前命中');
         patchVnode(oldStartVnode, newStartVnode)
         oldStartVnode = oldCh[++oldStartIdx];
         newStartVnode = newCh[++newStartIdx];
     } else if (checkSameVnode(oldEndVnode, newEndVnode)) {
         // 新后和旧后
         console.log('②新后和旧后命中');
         patchVnode(oldEndVnode, newEndVnode)
         oldEndVnode = oldCh[--oldEndIdx]
         newEndVnode = newCh[--newEndIdx]
     } else if (checkSameVnode(oldStartVnode, newEndVnode)) {
         // 新后和旧前
         console.log('③新后和旧前命中');
         patchVnode(oldStartVnode, newEndVnode)
         // 当③新后与旧前命中的时候，此时要挪动节点。挪动新前指向的这个节点到老节点的旧前的前面
         // parentElm.insertBefore(createElement(oldStartVnode))
         // 如何挪动节点？只有你插入一个曾经在 dom 树上的节点，它就会被挪动
         parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
         oldStartVnode = oldCh[++oldStartIdx]
         newEndVnode = newCh[--newEndIdx]
     } else if (checkSameVnode(oldEndVnode, newStartVnode)) {
         // 新前与旧后
         console.log('④新前与旧后命中');
         patchVnode(oldEndVnode, newStartVnode)
         // 当④新前与旧后命中的时候，此时要挪动节点。挪动新前指向的这个节点到老节点的旧前的后面
         // 如何挪动节点？只有你插入一个曾经在 dom 树上的节点，它就会被挪动
         parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
         oldEndVnode = oldCh[--oldEndIdx]
         newStartVnode = newCh[++newStartIdx]
     } else {
         // 都没有找到
         // 寻找 key 的 map
         if (!keyMap) {keyMap = {};
             // 从 oldStartIdx 开始，到 oldEndIdx 完结，for (let i = oldStartIdx; i <= oldEndIdx; i++) {const key = oldCh[i].key;
                 if (key != undefined) {keyMap[key] = i
                 }
             }
         }
         console.log(keyMap)
         // 寻找以后这项（newStartIdx）这项在 keyMap 中的映射的地位序号
         const idxInOld = keyMap[newStartVnode.key];
         console.log(idxInOld);
         if (idxInOld == undefined) {
             // 判断，如果 idxInOld 是 undefined 示意它是全新的项
             // 被退出的项（就是 newStartVnode 这项）当初不是真正的 dom 节点
             parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
         } else {
             // 如果不是 undefined，不是全新的项，而是要挪动
             const elmToMove = oldCh[idxInOld];
             patchVnode(elmToMove, newStartVnode); // 老的在前，新的在后
             // 把这项设置为 undefined，示意曾经解决完这项了
             oldCh[idxInOld] = undefined;
             // 挪动，调用 insertBedore 也能够实现挪动
             parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
         }
         // 指针下移，只挪动新的头
         newStartVnode = newCh[++newStartIdx];
         // newStartIdx++;
     }
 }
 // 持续看看有没有残余的，循环完结了 start 还是比 old 小
 if (newStartIdx <= newEndIdx) {console.log('new 还有残余节点没有解决, 要加项。要把所有的残余节点插入到 oldSartVnode 之前')
     // 这时须要看以后的子节点，作为插入的标杆
     // let before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
     // console.log(before)
     // 遍历新的 newch，增加到老的没有解决的之前
     for (let i = newStartIdx; i <= newEndIdx; i++) {
         // insertBefore 办法能够自动识别 null，如果是 null 就会主动排到队尾去，和 appendChild 是统一的了
         // newCh[i] 当初还没有真正的 dom，所以要调用 createElement()函数变为 dom
         parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);
     }
 } else if (oldStartIdx <= oldEndIdx) {console.log('old 还有残余节点没有解决，阐明须要删除节点，（要删除项）')
     // 批量删除 oldStart 和 oldEnd 指针之间的项
     for (let i = oldStartIdx; i <= oldEndIdx; i++) {if (oldCh[i]) {parentElm.removeChild(oldCh[i].elm)
         }

     }
 }
}

function checkSameVnode (a, b) {return a.sel === b.sel && a.key === b.key}

新前新的没有解决的虚构节点的结尾，旧前就是旧的没有解决的虚构节点；
新后就是新的没有解决的虚构节点的最初一个，旧后就是旧的没有解决的虚构节点的最初一个；
以上代码总结来说就是 子节点更新策略 的四种命中形式：
①新前与旧前
②新后与旧后
③新后与旧前
④新前与旧后
命中一种就不再进行命中判断了
节点的操作分为以下几种，通过几个例子阐明：
1)新增的状况

新前节点与旧前节点进行比照是不是同一个节点，如果是同一个节点，那就不是新增也不是删除，而是更新，不须要进行节点挪动操作，而是更新节点，此时命中①；旧前与新前同时指针下移一位，再次比拟，新前等于新后或旧前等于旧后循环完结
While(新前 <= 新后 && 旧前 <= 就后) {
}
如果是旧节点先循环结束，而新节点还有残余，则阐明新节点中残余节点是须要被新增的
2) 删除的状况

A，B 旧前与新前比拟，雷同，此时旧前指针指向 D, 新前指针指向 D，没有命中，此时开启新后与旧后（命中②）比拟，旧后的 D 与新后的 D 比拟，命中之后，两个后节点往上走，此时旧后指向 C，新后指向 B，毁坏了循环规定(前 < 后)，完结循环，此时新节点循环结束
如果是新节点先循环结束，如果旧节点中还有残余节点，阐明它们是要被删除的节点
3) 多删除的状况

旧前与新前开始比照到 B，此时旧前指针指向 C, 新前指针指向 D，没有命中，此时开启新后与旧后（命中②）比拟，旧后的 E 与新后的 D 比拟，没有命中，此时开启新后与旧前的比拟（命中③），新后的 D 与旧前的 C 比拟，没有命中，此时开启新前与旧后（命中④）比拟，新前的 B 与旧后的 C 比拟，依然没有命中
如果是新节点先循环结束，如果老节点中还有残余节点（旧前和新后指针两头的节点，阐明他们是要被删除的节点）
4)删除且从新排序

当④新前与旧后命中的时候，此时要挪动节点。挪动 新前指向的这个节点 到老节点的旧前 的后面
5) 倒序重新排列

当③新后与旧前命中的时候，此时要挪动节点。挪动 新前指向的这个节点 到老节点的旧前 的前面
如果都没有命中，就须要用循环来寻找了，循环旧节点，如果新节点中没有，就将旧节点中此个设为 undefined
四断定还有残余项：
①如果是旧节点先循环结束，阐明新节点中有要插入的节点
②如果是新节点先循环结束，如果老节点中还有残余节点，阐明他们是要被删除的节点
以上就是 diff 算法剖析我集体的学习与解读了总结下来就是：先通过 h 函数创立虚构 dom，而后调用 patch 函数进行新旧虚构 DOM 的粗略比拟是否为同一个节点，若是暴力插入新的，删除旧的节点；不是同一个节点则进行精细化比拟 patchVnode，以新节点为参照，先看新节点是不是单纯的 dom 节点（即有 text 无 children），若是则更新旧的节点内容为新的节点 text 属性值；若不是（即有 children），再看旧的节点是否有子节点，若没有，则将新节点的子节点循环插入到旧节点中；若旧节点也有子节点，那么对于新旧所有的子节点开启新一轮的精细化比拟 updateChildren，即子节点更新策略（利用 js 的指针思维以及四种命中形式），比拟完之后将须要更新的节点上树，追加到实在的 DOM 上。
残缺代码：虚构 dom 与 diff 算法