【Vue】源码—虚拟DOM和diff算法
github源码链接：虚拟DOM和diff算法
1.理解虚拟DOM和diff算法
1.1什么是虚拟DOM？
从本质上来说，虚拟DOM是一个JavaScript对象，通过对象的方式来表示DOM结构。将页面状态抽象为JS对象的形式，配合不同的渲染工具，使跨平台渲染成为可能。虚拟DOM是DOM的抽象，这个对象是更加轻量级的对DOM的描述。
1.2 为什么要用虚拟DOM？
1. 保证性能下限，在不进行手动优化的情况下，提供过得去的性能。
对比一下修改DOM时真实DOM操作和虚拟DOM的过程，来看一下它们重排重绘的性能消耗：
- 真实DOM：生成HTML字符串+重建所有的DOM元素
- 虚拟DOM：生成vNode+DOMdiff+必要的dom更新
虚拟DOM的更新DOM的准备工作耗费更多的时间，也就是JS层面，相比于更多的DOM操作它的消费是极其便宜的。尤雨溪在社区论坛中说道：框架给你的保证是，你不需要手动优化的情况下，依然可以给你提供过得去的性能。
2. 跨平台
虚拟DOM本质上是JavaScript的对象，它可以很方便的跨平台操作。比如服务器渲染、uniapp等
1.3diff算法简介
新虚拟DOM和旧虚拟DOM进行diff(精细化比较),算出应该如何最小量更新，最后反映到真正的DOM上【虚拟节点变成DOM节点】在Vue里面叫做patch
1.4diff算法原理
在新老虚拟DOM进行对比：
- 首先，对比节点本身，判断是否为同一节点，如果不为相同节点，则删除该节点重新创建节点进行替换
- 如果为相同节点，进行patchVnode，判断如何对该节点的子节点进行处理，先判断一方有子节点一方没有子节点的情况(如果新的children没有子节点，将旧的子节点移除)
- 比较如果都有子节点，则进行updateChildren，判断如何对这些新老节点的子节点进行操作(diff核心)
- 匹配时，找到相同的子节点，递归比较子节点
在diff中，只对同层的子节点进行比较，放弃跨级的节点比较，使得时间复杂度降低至O(n),也就是说只有当新旧children都为多个子节点时才需要用diff算法进行精细化比较。
1.5diff算法什么时候执行？
在页面首次渲染的时候会调用一次patch并创建新的vnode，不会进行更深层次的比较
然后在组件中数据发生变化时，会触发setter然后通过notify通知Watcher，对应的Watcher会通知更新并执行更新函数，它会执行render函数获取新的虚拟DOM，然后执行patch对比上次渲染结果的老的虚拟DOM，并计算出最小的变化，然后再去根据这个最小的变化去更新DOM
1.6diff算法的优化
1.只比较同一层级，不跨级比较
diff过程只会把同颜色并且同一层级的DOM进行比较，这样能够简化比较次数
2.比较标签名
如果同一层级的标签名不同，就直接移除老的虚拟DOM对应的节点，不继续按这个树状结构左深度比较。
3.比较key
如果标签名相同，key也相同，就会认为是相同节点，也不继续按这个树状结构做深度比较。
key的作用
比如有一个列表，我们需要在中间插入一个元素，会导致后面的元素进行重新渲染。如图li1,li2不会重新渲染，li3,li4,li5都会重新渲染。
因为在不使用key或列表的index作为key的时候，每个元素对应的位置关系都是index，上图中的结果导致我们插入的元素到后面的全部元素，对应的位置关系都发生了变更，所以全部都会执行更新操作，而我们希望的是只渲染添加的元素，其他的元素不再进行重新渲染。
而再使用唯一key的情况下，每个元素对应的位置关系都是key，看一下使用唯一key值的情况下，这样图中的li3和li4就不会重新渲染，因为元素内容没有发生改变，对应的位置关系也没有发生改变。
因此，不建议使用index作为key。
原因是：使用index作为key和没写基本上没区别。因为不管数组的顺序怎么颠倒，index都是0,1,2...这样排列，导致Vue会复用错误的旧子节点，做很多额外的工作。
总结：
- 在diff算法中，key是vnode的唯一标记，key的作用主要是为了更高效的更新虚拟DOM，因为它可以非常精确的找到相同节点，因此patch过程会非常高效
- Vue在patch过程中会判断两个节点是不是相同的节点时，key是一个必要条件。在渲染列表时，如果不写key，Vue在比较的时候，就可能会导致频繁更新元素，使整个patch过程比较低效，影响性能。
- 应该避免使用数组下标作为key，因为key值不是唯一的话，也可能会出现上面图中的问题，还有比如在使用相同标签元素过渡切换的时候，就会导致只替换其内部属性，而不会触发过渡效果。这个时候key的作用是用来表示一个独立的元素。
- Vue判断两个节点是否相同时，主要判断两者的元素类型和key等。因为带key就不是就地复用。在checkSameVnode函数中a.key===b.key对比中可以避免就地复用。所以会更加准确。
2.实现虚拟DOM和diff算法
3.1h函数【简易版】
用来产生虚拟节点(vnode)
- 判断第三个参数是否是一个字符串或是数字。如果是字符串或数字，直接返回vnode
- 判断第三个参数是否是一个数组。声明一个数组，用于存储子节点，需要遍历数组，这里需要判断每一项是否是一个对象(因为vnode返回一个对象并且一定会有sel属性)，但是不需要执行每一项，因为在数组中已经执行了h函数。其实，并不是函数递归进行调用(自己调用自己)，而是一层一层的嵌套
- 判断第三个参数是否是一个对象。直接将这个对象赋值给children，并返回vnode
import vnode from './vnode';
// 这个函数必须接受3个参数，缺一不可
// 相当于它的重载功能较弱
/*
* 也就是说，调用的时候形态必须是下面的三种之一:
* 形态一：h('div', {}, '文字');
* 形态二：h('div', {}, []);
* 形态三：h('div', {}, h());
*/
export default function(sel, data, c) {
// 检查参数的个数
if(arguments.length != 3) {
throw new Error('h() takes exactly 3 arguments');
}
// 检查参数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.hasOwnProperty('sel'))) {
throw new Error('h() takes an array of objects or selectors');
}
children.push(c[i]);
}
// 循环结束了，就说明children收集完毕，此时可以返回虚拟节点，有children属性
return vnode(sel, data, children, undefined, undefined);
} else if(typeof c == 'object' && c.hasOwnProperty('sel')) {
// 说明现在调用h函数是形态三
// 传入的c是唯一的children,不用执行c，因为测试语句中已经执行了c
let children = [c];
} else {
throw new Error('此h函数必须传入三个参数')
}
}
3.2vnode函数
用于创建虚拟节点
export default function(sel, data, children, text, elm) {
const key = data.key;
// sel 选择器， data 属性， children 子节点，text 文本内容， elm 虚拟节点绑定的真实DOM节点
return {
sel,
data,
children,
text,
elm,
key
}
}
3.3patch函数
首先判断旧节点是否是虚拟节点，不是则将旧节点变为虚拟节点【vnode函数】，如果是则判断是否是同一个节点类型，在这个判断中是则进行精细化比较，不是则进行暴力删除
import vnode from "./vnode";
import createElement from "./createElement";
import patchVnode from "./patchVnode";
export default function(oldVnode, newVnode) {
// 判断传入的第一个参数，是DOM节点还是虚拟节点?
if(oldVnode.sel == '' || oldVnode.sel == undefined) {
// 传入的第一个参数是DOM节点，此时要包装为虚拟节点
// toLowerCase()变成小写字母
oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], undefined, oldVnode);
}
// 判断oldVnode和newVnode是不是同一个节点
if(oldVnode.key == newVnode.key && oldVnode.sel == newVnode.sel) {
patchVnode(oldVnode, newVnode);
} else {
console.log('暴力插入新的，删除旧的');
// 需要.elm得到
let newVnodeElm = createElement(newVnode);
if(oldVnode.elm.parentNode && newVnodeElm) {
// 插入到老节点之前
oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
}
// 删除老节点
oldVnode.elm.parentNode.removeChild(oldVnode.elm);
}
}
补充知识
appendChild():
是在父节点中的子节点列表的末尾添加新的节点(相对于父节点来说)【添加后属于父子关系】
insertBefore():
是在已有的节点前添加新的节点(相对于子节点来说)【添加后属于兄弟关系】
parentNode属性:
该属性可指定元素对象后获取该元素的父节点元素
3.4createElement函数
将vNode转换为真实DOM【上树】
- 首先获取新虚拟节点的sel属性，并且为他创建真实的DOM节点
- 紧接着判断是有子节点还是有文本，文本直接进行上树
- 如果是是子节点，则进入for循环中，获取children中的第一项，并调用createElement函数为该子节点创建真实DOM，执行完第一项返回创建的虚拟DOM，然后使用appendChild方法追加到domNode【最开始创建的的真实DOM】，依次类推，执行后面的数组项。
- 最后，将创建好的所有真实的DOM返回回去，在patch函数中进行上树
//真正创建节点.将vnode创建为DOM
export default function createElement(vnode){
//创建一个DOM节点，现在这个节点还是孤儿节点，不进行插入
let domNode = document.createElement(vnode.sel)
//有子节点还是有文本
if(vnode.text != '' && (vnode.children == undefined || vnode.children.length == 0)){
//文本-使用innerText直接进行上树
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 children = vnode.children[i];
console.log(children);
//创建出它的DOM，一旦调用createElement意味着：创建出DOM了，并且他的elm属性指向了
//创建出的DOM，但是还没有上树，是一个孤儿节点
let chDOM = createElement(children);
//上树
domNode.appendChild(chDOM)
}
}
//补充elm属性
vnode.elm = domNode;
//返回elem，elm属性是个纯DOM对象
return vnode.elm;
}
3.5patchVnode函数
patchVnode函数的主要作用是：
- 首先判断newVnode和oldVnode是否指向同一个对象，如果是，则直接return
- 如果它们都有text并且都不相等或者oldVnode有子节点而newVnode没有，那么将oldVnode.elm的文本节点设置为newVnode的文本节点
- 如果oldVnode没有子节点而newVnode有，则将newVnode的子节点变成真实DOM之后添加到oldVnode.elm后面
- 如果两者都有子节点，则执行updateChildren函数比较子节点-四种优化策略 【重要！！！】
import createElement from "./createElement.js";
import updateChildren from './updateChildren.js'
//对比同一个虚拟节点
export default function patchVnode(oldVnode,newVnode){
//判断新旧vnode是否是同一个对象
if(oldVnode === newVnode) return;
//判断新vnode有没有text属性
if(newVnode.text != undefined && (newVnode.children === undefined || newVnode.children.length == 0)){
//新vnode有text属性
//console.log('新vnode有text属性')
if(newVnode.text !== oldVnode.text){
//如果新虚拟节点中的text和老的虚拟节点的text不同，那么直接让新的text写入老的elm中即可。如果老的elm中是children，那么也会立即消失
oldVnode.elm.innerText = newVnode.text
}
} else {
//新节点没有text属性
//console.log('新节点没有text属性')
//判断老的有没有children
if(oldVnode.children != undefined && oldVnode.children.length > 0){
//老的有children，此时就是最复杂的情况，新老都有children
updateChildren(oldVnode.elm,oldVnode.children,newVnode.children)
}else{
//老的没有children，新的有children
//情况老节点内容
oldVnode.elm.innerHTML = '';
//遍历新的vnode子节点，创建DOM，上树
for(let i = 0;i<newVnode.children.length;i++){
let dom = createElement(newVnode.children[i]);
// elm 虚拟节点绑定的真实DOM节点
oldVnode.elm.appendChild(dom)
}
}
}
}
3.6 updateChidren函数
这个是新的vnode和oldVnode都有子节点，且子节点不一样的时候进行对比子节点的函数，在这个过程中进行精细化比较，然后更新子节点。
精细化比较是diff算法中的四种优化策略，这里将使用双指针的进行进行diff算法的比较，能够有效加快diff效率。
四种优化策略：(前提：sel和key都要相同)
【只有当第一种不命中的时候，才会采取第二种，依次类推，如果四种都不命中，则需要通过循环来查找。命中指针才会进行移动，否则不移动】
①新前与旧前
②新后与旧后
③新后与旧前 【将新后newEnd指向的节点移动到旧后oldEnd之后】
④新前与旧后 【将新前newStart指向的节点移动到旧前oldStart之前】
对比流程：
①依次比较，当比较成功后退出比较
②渲染结果以newVnode为准
③每次比较成功后start点和end点向中间靠拢
④当新旧节点中有一个start点跑到end点右侧时终止比较
⑤如果都匹配不到，则旧虚拟DOMkey值去比对新虚拟DOM的key值，如果key相同则复用，并移动到新虚拟DOM的位置
import patchVnode from "./patchVnode";
import createElement from "./createElement";
// 判断是不是同一个虚拟节点
function checkSameVnode(a, b) {
return a.sel == b.sel && a.key == b.key && a.key;
}
export default function updateChildren(parentElm, oldCh, newCh) {
console.log('update');
// 旧前
let oldStartId = 0;
// 新前
let newStartId = 0;
// 旧后
let oldEndId = oldCh.length - 1;
// 新后
let newEndId = newCh.length - 1;
// 旧前节点
let oldStartVnode = oldCh[0];
// 新前节点
let newStartVnode = newCh[0];
// 旧后节点
let oldEndVnode = oldCh[oldEndId];
// 新后节点
let newEndVnode = newCh[newEndId];
let keyMap = null;
while(oldStartId <= oldEndId && newStartId <= newEndId) {
// 首先不是判断一二三四命中，而是要略过已经加undefined标记的东西
if(oldStartVnode == null || oldCh[oldStartId] == undefined) {
oldStartVnode = oldCh[++oldStartId];
} else if(oldEndVnode == null || oldCh[oldEndId] == undefined) {
oldEndVnode = oldCh[--oldEndId];
} else if(newStartVnode == null || newCh[newStartId] == undefined) {
newStartVnode = newCh[++newStartId];
} else if(newEndVnode == null || newCh[newEndId] == undefined) {
newEndVnode = newCh[--newEndId];
} else if(checkSameVnode(oldStartVnode, newStartVnode)) {
console.log('①');
// 对比
patchVnode(oldStartVnode, newStartVnode);
// 指针后移[先后移后使用]
oldStartVnode = oldCh[++oldStartId];
newStartVnode = newCh[++newStartId];
} else if(checkSameVnode(oldEndVnode, newEndVnode)) {
console.log('②');
// 新后和旧后
patchVnode(oldEndVnode, newEndVnode);
oldEndVnode = oldCh[--oldEndId];
newEndVnode = newCh[--newEndId];
} else if(checkSameVnode(oldStartVnode,newEndVnode)) {
// 新后与旧前
console.log('③');
patchVnode(oldStartVnode, newEndVnode);
// 当新后与旧前命中的时候，此时要移动节点，移动新前指向的这个节点到老节点的旧后的后面【当前最后一个未处理的节点】
// 为什么没有使用appendChild，是因为appendChild是所有子元素的前面，而就后不一定是所有子元素后面
// 如何移动节点？只要你插入一个已经在DOM树上的节点，它就会移动
// elm 虚拟节点绑定的真实DOM节点
// nextSibling属性返回元素节点之后的下一个兄弟节点(包括文本节点、注释节点)
parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling);
oldStartVnode = oldCh[++oldStartId];
newEndVnode = newCh[--newEndId];
} else if(checkSameVnode(oldEndVnode,newStartVnode)) {
console.log('④');
patchVnode(oldEndVnode,newStartVnode);
// 当新前与旧后命中的时候，此时要移动节点，移动新前指向的这个节点到老节点的旧前的前面
parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm.nextSibling);
oldEndVnode = oldCh[--oldEndId];
newStartVnode = newCh[++newStartId];
} else {
// 四种命中都没有命中
// 寻找key的map
// 为old节点制作keyMap一个映射对象，这样就不用每次都遍历老对象
if(!keyMap) {
keyMap = {};
// 从oldStartId开始，到oldEndId结束，创建keyMap映射对象
for(let i = oldStartId; i <= oldEndId; i++) {
const key = oldCh[i].key;
if(key != undefined) {
keyMap[key] = i;
}
}
}
// 寻找当前这项(newStartId)这项在keyMap中的映射的位置序号
const idInOld = keyMap[newStartVnode.key];
console.log(idInOld);
if(idInOld == undefined) {
// 判断，如果idInOld是undefined表示它是全新的项
// 被加入的项(就是newStartVnode这项)现在不是真正的DOM节点
parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm);
} else {
// 如果不是undefined,不是全新的项，而是要移动
// 存储移动的项
const elmToMove = oldCh[idInOld];
patchVnode(elmToMove, newStartVnode);
// 把这项设置为undefined,表示我已经处理完这项了
oldCh[idInOld] = undefined;
// 移动，调用insertBefore也可以实现移动
parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm);
}
// 指针下移，只移动新的头
newStartVnode = newCh[++newStartId];
}
}
// 继续看看有没有剩余的,循环结束了start还是比old小，说明有新增项
// 因此需要插入这些节点
if(newStartId <= newEndId) {
console.log('new还有剩余节点没有处理,要加项。要把所有剩余的节点都插入到oldStartId之前');
// 插入的标杆，因为在插入之前可能会存在新后和旧后的对比，你需要确定新后和旧后对比的最后一次，插入到最后一次之前
// 遍历新的newCh，添加老的没有处理的之前
for(let i = newStartId; i <= newEndId; i++) {
console.log('新增');
// insertBefore方法可以自动识别null，如果是null就会自动排到队尾去，和appendChild是一致的
// newCh[i]现在还没有真正的DOM，所以要调用createElement()函数变为DOM
parentElm.insertBefore(createElement(newCh[i]), oldCh[oldStartId].elm);
}
} else if(oldStartId <= oldEndId) {
// 只能删除中间项，不能删除最后一项
console.log('old还有剩余节点没有处理');
// 表示有删除节点
// 批量删除oldStart和oldEnd指针之间的项
for(let i = oldStartId; i <= oldEndId; i++) {
if(oldCh[i]) {
parentElm.removeChild(oldCh[i].elm);
}
}
}
}
总结
在JavaScript中，渲染DOM的开销是非常大的，比如我们修改了某个数据，如果直接渲染到真实的DOM，会引起整个DOM树的回流和重绘。
因此我们需要通过虚拟DOM和diff算法进行优化，只更新修改部分，实现最小量更新。
此时我们需要根据真实DOM生成虚拟DOM，当虚拟DOM某个节点的数据改变后会生成一个新的vnode，然后新vnode和旧vnode进行比较，发现有不一样的地方就直接修改到真实DOM上，然后使旧vnode变成新vnode。
diff算法的过程就是patch函数的调用，比较新旧节点。
在采用diff算法比较新旧节点的时候，只会进行同层级的比较。
在patch方法中，首先先比较新旧虚拟节点是否是同一个节点，如果不是同一个节点，那么就会将旧的节点删除掉，插入新的虚拟节点，然后再使用createElement函数创建其真实DOM，将其渲染到真实的DOM树。
如果是同一个节点，使用patchVnode函数比较新旧节点，包括属性更新、文本更新、子节点更新。
但如果新旧节点都有子节点，则需要进行diff算法，调用updateChildren函数，如果新节点没有文本内容而旧节点有文本内容，则需要将旧节点文本内容删除，如果新节点有文本内容，则直接进行替换。
uppdateChildren方法将新旧节点的子节点提取出来，使用的是双指针的方式进行四种优化策略的循环比较。
①新前与旧前比较；②新后与旧后比较；③新后与旧前比较；④新前与旧后比较。
如果四种优化策略方法均没有命中，则会进行遍历方法进行比较(源码中使用Map对象进行缓存，加快了比较的速率),如果设置了key，就会使用key进行比较，找到当前的新节点的子节点在Map中的映射位置，如果不存在，则需要添加节点，存在则需要移动节点。最后循环结束之后，如果新节点还有剩余节点，则说明需要添加节点，如果旧节点还有剩余，则说明需要删除节点。
转载自:https://juejin.cn/post/7166852464979738661