面试中如果你简历上写了掌握React，那面试官肯定会让你说一下dom-diff算法的过程，
那么今天就实现一个简单的dom-diff算法。
虚拟DOM
必须先说一下虚拟DOM的概念，virtual dom，就是虚拟节点。是通过js中的Object对象来模拟DOM中的节点，再通过特定的渲染方法render()将其转化渲染成真实的DOM节点。
一个虚拟DOM节点大概长这样：
{
type:’节点类型‘, //ul,div,li,text等等
children:[], //当前节点包含的子节点集合,内部结构也是虚拟DOM节点组成的数组
props:{}, //属性键值对
}
//虚拟DOM元素的类：
class Element{
constructor(type, props, children){
this.type = type;
this.props = props;
this.children = children;
}
}
那么我们就需要一个方法，创建虚拟DOM节点，并生成这样结构的对象；
function createElement(type, props, children){
return new Element(type, props, children);
}
生成虚拟DOM
我们想在页面中创建一个ul列表，如下图所示，其中包含三个li元素，每个li中分别包含文本a, b, c，ul,li的属性分别设置为class的值 为list以及 item, 用上面的方法如何生成虚拟DOM节点呢?
virualDom01.png
let virtualDom1 = createElement('ul', { class: 'list'}, [
createElement('li', { class: 'item', ['a']}),
createElement('li', { class: 'item', ['b']}),
createElement('li', { class: 'item', ['c']}),
])
代码参考：生成虚拟DOM节点
render
render方法实现的功能是 将虚拟DOM转化成 真实DOM，我们可以想到一个方法那就是利用createElement 以及 appendChild。
/**
* @vnode就是一个Element结构的对象
{
type,
props,
children,
}
*/
function render(vnode) {
//1. 根据虚拟DOM的节点类型创建一个该类型的元素
let element = document.createElement(vnode.type);
//2. 遍历其属性并绑定
for (let key in vnode.props) {
//绑定属性
setAttr(element, key, vnode.props[key]);
}
// .....
return element;
}
}
设置属性的方法
/*
* node:根据类型已经创建的真实节点
* 属性类型暂时包含：value值, style样式，还有其它比如class等。
*/
function setAttr(node, key, value){
switch(key){
case 'value':
let tagName = node.tagName.toUpperCase();
//如果是文本框或文本区域则直接将值赋给它的value属性
if(/^(INPUT|TEXTAREA)$/.test(tagName)){
node.value = value;
}else {
node.setAttribute(key, value);
}
break;
case 'style':
//如果是内联样式属性则赋值给node.style.cssText属性
node.style.cssText = value;
break;
default:
node.setAttribute(key, value);
break;
}
}
接下来就是对vnode的children子节点的渲染，我们知道一个思路，如果子节点仍然是Element类型，即虚拟DOM元素，则需要继续进行递归render转化,于是在render方法中还需要：
//3. 遍历children子元素
(vnode.children || []).forEach(child =>{
child = (child instanceof Element)? render(child): document.createTextNode(child);
element.appendChild(child);
})
最后转换成为真实DOM的节点还差一步就可以渲染到页面中：
//渲染节点, 将虚拟dom渲染成真实DOM
function renderDOM(elements, target){
target.appendChild(elements);
}
参考代码：render
DOM-DIFF
DOM-DIFF就是一种比较算法,比较两个虚拟DOM的区别，也就是比较两个对象的区别。
也有真实DOM与虚拟DOM的比较，不过我们这里先只讨论虚拟DOM之间的比较。
DOM-DIFF的过程
DOM-DIFF作用是通过js层面的计算，根据两个虚拟对象创建出差异的补丁对象patch，用来描述改变了哪些内容，然后用特定的操作解析patch对象，更新dom完成页面的重新渲染。
那我们按照下图的变更来实现一个DOM-diff的过程：
图2-diff新旧树对比.png
DOM-DIFF三种优化策略
-
只比较平级
规则一：只比较平级
-
不会跨级比较
规则二：不跨级
-
同一级的变化节点，如果节点相同只是位置交换，则会复用。
规则三：同级易位可复用
PS:通过key来实现。
差异计算
-
先序深度优先遍历
遍历次序深度优先遍历.png
- JS对象模拟并生成虚拟DOM
- 将虚拟DOM转成真实DOM并插入到页面中
- 若事件触发了虚拟DOM的变更，则比较两棵虚拟DOM树的差异，得到差异对象patch
- 把差异对象patch应用到真实的DOM树中渲染。
差异对象patch
/*
* 递归树，比较后的结果放到补丁包中
* * 规则：
* 1. 结点类型type相同时，则看props是否相同。产生一个属性补丁包{ type:'ATTRS',attrs:{ class: 'list-group'}}
* 2. 新dom结点不存在的情况， { type:' REMOVE', index:xxx }
* 3. 结点类型不相同，直接替换, { type:'REPLACE', newNode: newNode}
* 4. 文本的变化， { type:'TEXT', text: 1}
*/
//生成补丁包
function generate(oldNode, newNode, index, patches){
//每个元素都有补丁对象
let currentPatch = [];
//规则2：新节点不存在的情况
if(!newNode){
currentPatch.push({type:'REMOVE', index});
} else if(diffToos.isString(oldNode) && diffTools.isString(newNode)){
//规则4：文本节点变化
currentPatch.push({ type: 'TEXT', text:newNode});
} else if(newNode.type === oldNode.type){
//规则1：节点类型相同，比较属性
let attrs = diffTools.attrs(oldNode.props, newNode.props);
//获取到的差异属性放到当前节点的补丁包中
if(Object.keys(attrs).length >0){
currentPatch.push({type:'ATTRS', attrs});
}
//若有子节点，则继续比较
diffTools.child(oldNode.children, newNode.children, index, patches);
}else {//规则3： 节点类型不相同，直接替换
currentPatch.push({type:'REPLACE', newNode});
}
//TODO 如果平级元素互换，会导致重新渲染，其实移动一下就可以
//TODO 新增节点也不会被更新
//最后如果当前节点的补丁包中有内容,则将其放入整棵树的补丁包中
if(currentPatch.length){
patches[index] = currentPatch;
}
}
打补丁时需要的工具集
/*
* 一些比较时用到的工具
*/
let Index = 0;
let diffTools = {
//判断节点是否为文本节点
isString(node){
return Object.prototype.toString.call(node) == '[object String]';
},
//比较新旧属性差异，并返回最终要修改的属性
attrs(oldProps, newProps){
let patch = {};
//依次遍历新旧节点属性
for(let key in oldProps){
//1. 若旧属性与新属性不同或者在新属性中不存在，即为删除或变更
patch[key] = newProps[key]; //则以新的为准；
}
for(let key in newProps){
//1. 若新属性在旧属性中不存在，即为追加
if(!oldProps.hasOwnProperty(key)){
patch[key] = newProps[key]; //也以新的为准
}
}
return patch;
},
//继续比较子节点
child(oldChild,newChild, index, patches){
oldChild.forEach((child, idx)=>{
//每一层比较，使用同一Index,所以用全局的Index
generate(child, newChild[idx], ++Index, patches);
})
}
}
比较方法
维护两树不同的补丁包
function diff(oldTree, newTree){
//两树的差异补丁包
let patches = {};
let index = 0; //默认从第0个节点开始比较
generate(oldTree, newTree, index, patches);
return patches;
}
最后模拟两棵不同的树结构，并打印出补丁包
let virtualDom1 = createElement('ul', { class: 'list'}, [
createElement('li',{class:'item'}, ['a']),
createElement('li',{class:'item'}, ['b']),
createElement('li',{class:'item'}, ['c'])
]);
let virtualDom2= createElement('ul', { class: 'list'}, [
createElement('li',{class:'item'}, ['1']),
createElement('li',{class:'item-active'}, ['b']),
createElement('div',{class:'item-div'}, ['3']),
]);
let el = render(virtualDom1);
let patches = diff(virtualDom1, virtualDom2);
console.log('打印出补丁包’, patches);
renderDOM(el, window.root);
代码参考：diff比较生成差异补丁包
打补丁
现在还差一步，就是打补丁
//打补丁规则
function doPatch(node, patches){
patches.forEach(patch =>{
//补丁根据类型，ATTRS,TEXT,REPLACE,REMOVE
switch(patch.type){
case 'ATTRS':
for(let key in patch.attrs){
let value = patch.attrs[key];
if(value){
setAttr(node, key,value);
}else {
node.removeAttribute(key);
}
}
break;
case 'TEXT':
node.textContent = patch.text;
break;
case 'REPLACE':
let newNode = (patch.newNode instanceof Element)?
render(patch.newNode): document.createTextNode(patch.newNode);
//用新节点替换
node.parentNode.replaceChild(newNode, node)
break;
case 'REMOVE':
node.parentNode.removeChild(newNode, node)
break;
default:
break;
}
})
}
现在就是依次遍历需要变更的元素并执行打补丁的操作
//依次打补丁
let patchIndex = 0;
function patch(node, patches){
let currentPatch = patches[patchIndex ++]
let childNodes = node.childNodes;
childNodes.forEach(child=>{
patch(child, patches);
});
if(currentPatch){
doPatch(node, currentPatch);
}
}
把补丁包给目标元素打上，并更新视图：
patch(el, patches);
代码参考：打补丁
简易版的DOM-diff就到这里，目前还有一些关于key的优化以及同级元素易位只需替换的逻辑还未实现。
等下一篇再深入去实现并练习。
网友评论