vue2 diff算法及虚拟DOM

概括：diff算法，虚拟DOM中采用的算法，把树形结构按照层级分解，只比较同级元素，不同层级的节点只有创建和删除操作。

一、虚拟DOM

(1) 什么是虚拟DOM？

虚拟 DOM (Virtual DOM，简称 VDOM) 是一种编程概念，意为将目标所需的 UI 通过数据结构“虚拟”地表示出来，保存在内存中，然后将真实的 DOM 与之保持同步。这个概念是由 React 率先开拓，随后在许多不同的框架中都有不同的实现，当然也包括 Vue。

虚拟DOM本质上就是用来描述真实DOM的JavaScript对象。

举例：

    <div id="hello">我是奥特曼</div>

编译成虚拟DOM

const vnode = {type: 'div',props: {id: 'hello'},children: [/* 更多 vnode */],text:'我是奥特曼'
}

（2）为什么要有虚拟DOM

1.能够减少操作真实DOM，对于浏览器而言有很大的性能提升，对于开发而言有很大的工作效率(同时避免了代码繁琐)。

2.想要修改数据 直接修改js对象即可，当然我们基于框架去开发也不用关心数据如何去更新视图。

3.例如新节点中，只有一部分节点进行变动时，只需要更新要变更的一部分，另一部分完全可以使用之前的节点。也避免了全部更新渲染。

最终目的：新虚拟DOM和旧虚拟DOM 进行diff计算，（精细化比较），算出应该如何最小量更新，最后反应到真正的DOM上。

二、snabbdom

在vue2中diff算法借鉴了snabbdom库，这个库也就包含着如何生成虚拟DOM和diff算法。

方法包括：

h( ) 函数用来生成虚拟DOM

vnode( ) 函数 通过h调用vnode 达到返回虚拟DOM的格式

patch( ) 函数用来比较新旧节点是否是一个节点，如果不是进行暴力更新，如果是进行对比

patchVnode( ) 函数用来详细对比 当遇见新旧节点都是数组时调用updataChildren

updataChildren( ) 函数用来对比新旧节点都是数组的情况

createElement( ) 讲虚拟dom创建出真实dom

以下函数均为简单版实现核心  并为源码 

（1）h( )函数

h函数的使用方式：

import { h } from 'vue'// 除了 type 外，其他参数都是可选的
h('div')
h('div', { id: 'foo' })// attribute 和 property 都可以用于 prop
// Vue 会自动选择正确的方式来分配它
h('div', { class: 'bar', innerHTML: 'hello' })// class 与 style 可以像在模板中一样
// 用数组或对象的形式书写
h('div', { class: [foo, { bar }], style: { color: 'red' } })// 事件监听器应以 onXxx 的形式书写
h('div', { onClick: () => {} })// children 可以是一个字符串
h('div', { id: 'foo' }, 'hello')// 没有 prop 时可以省略不写
h('div', 'hello')
h('div', [h('span', 'hello')])// children 数组可以同时包含 vnode 和字符串
h('div', ['hello', h('span', 'hello')])

 当然传参的方式有很多，最普通的写法

 h(a,{},'文字')

当然第二个就可以去表示是参数的一些属性，当没有属性的时候你也可以不传，或者第二个参数可以传子集元素的集合等，  snabbdom就是在这方面做了很多个判断。

 h(a,'文字')

实现一个简单的h函数

当然如果你想了解的更透彻可以 clone snabbdom库的代码进行查看。

git clone https://github.com/snabbdom/snabbdom.git

由于snabbdom传参形式较多， 这里就实现一个简单的h函数，只实现三种场景

  ① h('div', {}, '文字')② h('div', {}, [h()])③ h('div', {}, h())

vnode( ) 函数

export default function vnode(sel, data, children, text, elm) {const key = data == undefined ? undefined : data.key;return { sel, data, children, text, elm, key };
}

vnode就是把传进来的参数以对象的形式返回出去，返回出一个vnode的形式

sel: 元素/标签

data：属性

children：子元素vnode的集合

text：文字

elm：节点

h( )函数

import vnode from "./vnode";
/*** 产生虚拟DOM树 返回的是一个对象* 低配版本的h函数，这个函数必须接受三个参数，缺一不可* @param {*} sel* @param {*} data* @param {*} c* 调用只有三种形态* ① h('div', {}, '文字')* ② h('div', {}, [h()])* ③ h('div', {}, h())*/
export default function (sel, data, c) {// 检查参数个数if (arguments.length !== 3) {throw new Error("请传入只三个参数！");}// 检查参数c的类型if (typeof c === "string" || typeof c === "number") {// 说明现在是 ① h('div', {}, '文字')return vnode(sel, data, undefined, c, undefined);} else if (Array.isArray(c)) {// 说明是 ② h('div', {}, [])let children = [];// 遍历 数组 cfor (let item of c) {// 如果是数组传入的项一定有sel属性 也就必须是h函数的格式 不考虑数组中有包含文字的情况if (!(typeof item === "object" && item.hasOwnProperty("sel"))) {throw new Error("传入的数组有不是h函数的项");}// 不用执行c[i], 调用的时候执行了，只要收集children.push(item);}return vnode(sel, data, children, undefined, undefined);} else if (typeof c === "object" && c.hasOwnProperty("sel")) {// 说明是 ③ h('div', {}, h())let children = [c];return vnode(sel, data, children, undefined, undefined);} else {throw new Error("传入的参数类型不对！");}
}

（2）createElement( )函数

把虚拟节点从（vnode）变成真实DOM元素

/*** 创建节点。将vnode虚拟节点创建为DOM节点* 是孤儿节点，不进行插入操作* @param {object} vnode * @returns {object} domNode 返回DOM节点*/
export default function createElement(vnode) {// 创建一个DOM节点，这个节点现在是孤儿节点，最后返回这个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) {// 说明内部是子节点，需要递归创建节点 // 遍历vnode.children数组for (let ch of vnode.children) {// 递归调用 创建出它的DOM，一旦调用createElement意味着创建出DOM了。并且它的elm属性指向了创建出的dom，但是没有上树，是一个孤儿节点let chDOM = createElement(ch);// console.log(ch);// 上树domNode.appendChild(chDOM);}}// 补充elm属性vnode.elm = domNode;// 返回domNode DOM对象return domNode;
}

（3）patch( )函数

patch函数基本上也是diff算法的核心，比较这新虚拟节点和旧虚拟节点的不同。

export default function patch(oldVnode, newVnode) {// 判断传入的第一个参数是 DOM节点 还是 虚拟节点if (oldVnode.sel == "" || oldVnode.sel === undefined) {// 说明是DOM节点，此时要包装成虚拟节点oldVnode = vnode(oldVnode.tagName.toLowerCase(), // sel{}, // data[], // childrenundefined, // textoldVnode // elm);}// 此时新旧节点都是虚拟节点了// 判断 oldVnode 和 newVnode 是不是同一个节点if (oldVnode.key === newVnode.key && oldVnode.sel === newVnode.sel) {console.log("是同一个节点，需要精细化比较");patchVnode(oldVnode, newVnode);} else {console.log("不是同一个节点，暴力插入新节点，删除旧节点");// 创建 新虚拟节点 为 DOM节点let newVnodeElm = createElement(newVnode);// 获取旧虚拟节点真正的DOM节点let oldVnodeElm = oldVnode.elm;// 判断newVnodeElm是存在的if (newVnodeElm) {// 插入 新节点 到 旧节点 之前oldVnodeElm.parentNode.insertBefore(newVnodeElm, oldVnodeElm);}// 删除旧节点oldVnodeElm.parentNode.removeChild(oldVnodeElm);}
}

注释写的比较详细，大致三部分：

1. 第一次有可能传入进来的是一个元素，因为第一次还没有节点，需要把元素包装成虚拟节点 vnode

2. 如果 旧虚拟节点和新虚拟节点key和元素标签一样时 可以进入深层比较 调用patchVnode函数

3. 否则把新节点创建成dom元素 插入到旧节点之前 并移除旧节点

（4）patchVnode( )函数

import updateChild from "./updateChildren";
import createElement from "./createElement";
export default function patchVnode(oldVnode, newVnode) {// 第一种情况 全都一样 不需要操作if (oldVnode == newVnode) return;// 第二种情况新节点是文字if (  newVnode.text != undefined && (newVnode.children == undefined || newVnode.children.length == 0) ) {// 如果旧节点文字不等于新节点文字 直接替换if (oldVnode.text != newVnode.text) {oldVnode.elm.innerText = newVnode.text;}// 第三种情况 新节点是数组} else {// 如果新旧节点都是数组  也是最复杂的情况if (oldVnode.children && oldVnode.children.length > 0) {updateChild(oldVnode.elm, oldVnode.children, newVnode.children);//   如果旧节点是文字 新节点是数组} else {// 清空旧节点文字 把子节点给旧节点的elm元素上oldVnode.elm.innerText = "";for (let i = 0; i < newVnode.children; i++) {const childDom = newVnode.children[i];childDom.elm = createElement(childDom);oldVnode.elm.appendChild(childDom.elm);}}}newVnode.elm = oldVnode.elm;
}

（5）updateChild( )函数

这也是函数中最复杂的部分了，如果新旧节点均为数组，我们要做最细致的比较。

例如：旧节点 A,B,C  新节点 A,C,B  我们是肯定希望去移动它，并不是删除B,C重新创建出C,B

例如： 旧节点 A,B,C  新节点 D,A,B,C,E  同样我们需要在A前面创建出D  在C后面创建出E 

当然复杂的场景还有很多很多，这也是我们都要考虑的，这时候就需要用到snabbdom中的四个指针概念了。

 那什么是新前旧前、新后旧后呢？

 新前就是新节点（newVnode）中第一个，旧前就是旧节点（oldVnode）中的第一个, 新后旧后同理。

 遵循四种查找方式

1. 例如 第一种查询方式  新前和旧前（A==B）匹配上了  newStartIdx 和 oldStartIdx 都进行 +1  这时候新前旧前指针进行移动，移动后重新执行四种命中方式，   直到四种命中方式都找不到为止。

2. 若四种命中方式都查不着不到，则需要在oldVnode中进行循环查找，找到则插入到oldStartIdx之前，若循环也找不到则 创建出新元素 插入到oldEenIdx之前。 

3. 若新节点中有剩余 代表要新增元素 把新前和新后中间的元素 创建出真实DOM 插入到新后位置的之前。

4.若旧节点中有剩余 代表要删除元素 把旧前和旧后中间的元素 进行删除。

注意：当命中③时 需要移动节点 将当前新指向节点移动到旧节点之后，当命中④时，需要移动节点 将新指向节点移到到旧节点之前。

下面来举一个全面的 场景 以此用到所有命中方便理解

当然 图中最后一步是找不到的场景，当然也有找到的场景，在代码中 在 keyMap 中进行查找 

例如 keyMap  = { A: 0,B:1,C:2 }  若匹配到了需要调用patchVnode函数 并且  需要移到指定的位置上，若匹配不上则插入到旧前节点之前。

export default function updataChild(parentElm, oldCh, newCh) {// 旧前let oldStartIdx = 0;// 新前let newStartIdx = 0;// 新后let newEndIdx = newCh.length - 1;// 旧后let oldEndIdx = oldCh.length - 1;// 旧前节点let oldStartVnode = oldCh[0];// 旧后节点let oldEndVnode = oldCh[oldEndIdx];// 新前节点let newStartVnode = newCh[0];// 新后节点let newEndVnode = newCh[newEndIdx];let keyMap = null;// 进入循环while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// debugger// 新前 旧前// 1. 如果相同在// 首先应该不是判断四种命中，而是略过已经加了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(" ①1 新前与旧前 命中");// 精细化比较两个节点 oldStartVnode现在和newStartVnode一样了patchVnode(oldStartVnode, newStartVnode);// 移动指针，改变指针指向的节点，这表示这两个节点都处理（比较）完了oldStartVnode = oldCh[++oldStartIdx];newStartVnode = newCh[++newStartIdx];} else if (checkSameVnode(oldEndVnode, newEndVnode)) {// 新后与旧后console.log(" ②2 新后与旧后 命中");patchVnode(oldEndVnode, newEndVnode);oldEndVnode = oldCh[--oldEndIdx];newEndVnode = newCh[--newEndIdx];} else if (checkSameVnode(oldStartVnode, newEndVnode)) {// 新后与旧前console.log(" ③3 新后与旧前 命中");patchVnode(oldStartVnode, newEndVnode);// 当③新后与旧前命中的时候，此时要移动节点。移动 新后（旧前） 指向的这个节点到老节点的 旧后的后面// 移动节点：只要插入一个已经在DOM树上 的节点，就会被移动parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);oldStartVnode = oldCh[++oldStartIdx];newEndVnode = newCh[--newEndIdx];} else if (checkSameVnode(oldEndVnode, newStartVnode)) {// 新前与旧后console.log(" ④4 新前与旧后 命中");patchVnode(oldEndVnode, newStartVnode);// 当④新前与旧后命中的时候，此时要移动节点。移动 新前（旧后） 指向的这个节点到老节点的 旧前的前面// 移动节点：只要插入一个已经在DOM树上的节点，就会被移动parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm);oldEndVnode = oldCh[--oldEndIdx];newStartVnode = newCh[++newStartIdx];} else {// 四种都没有匹配到，都没有命中console.log("四种都没有命中");// 寻找 keyMap 一个映射对象， 就不用每次都遍历old对象了if (!keyMap) {keyMap = {};// 记录oldVnode中的节点出现的key// 从oldStartIdx开始到oldEndIdx结束，创建keyMapfor (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];if (idxInOld === undefined) {// 如果 idxInOld 是 undefined 说明是全新的项，要插入// 被加入的项（就是newStartVnode这项)现不是真正的DOM节点parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);} else {// 说明不是全新的项，要移动const elmToMove = oldCh[idxInOld];patchVnode(elmToMove, newStartVnode);// 把这项设置为undefined，表示我已经处理完这项了oldCh[idxInOld] = undefined;// 移动，调用insertBefore也可以实现移动。parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);}// newStartIdx++;newStartVnode = newCh[++newStartIdx];}}// 如果新节点还有剩余  要新增if (newStartIdx <= newEndIdx) {console.log('新节点有剩余',newCh[newEndIdx+1]);let before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm;for (let i = newStartIdx; i <= newEndIdx; i++) {parentElm.insertBefore(createElement(newCh[i]), before);// parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartIdx].elm);}}else if (oldStartIdx <= oldEndIdx) {console.log("旧节点有剩余");for (let i = oldStartIdx; i <= oldEndIdx; i++) {parentElm.removeChild(oldCh[i].elm);}}
}function checkSameVnode(oldStartVnode, newStartVnode) {return (oldStartVnode.key == newStartVnode.key &&oldStartVnode.sel == newStartVnode.sel);
}