Vitural Dom & diff算法 (一) 伪代码实现
(点击上方公众号，可快速关注)
作者：大搜车前端团队博客
网址：http://f2e.souche.com/blog/react-vitural-dom-diffsuan-fa-wei-dai-ma-shi-xian/
前言：
读React 源码大概是最幸福的事情，因为在社区里有数之不尽的高手都会给出自己很独到的见解，即使有不懂的地方也会能找到前人努力挖掘的痕迹。我反问自己，然后即使在这样优越的环境下，还不去读源码，是不是就太懒了。 ＃ 我会乱说？ ＃
约定
这一篇都通过伪代码实现，保证首先从总体上走通流程，后面的篇章都是基于这样一个流程去实现。
开始之前
这里必须明确一个概念，所谓的 自定义标签 都是由很多原生标签诸如<div>去实现的。
因此自定义标签就可以想象成
<MyTag> <div class="MyTag">
<SomeTag></someTag> ===> <div class="someTag"></div>
</MyTag> </div>
流程
创建虚拟DOM
真实DOM 连接 虚拟DOM
视图更新
计算 [ 新虚拟DOM ] 和 [ 旧虚拟DOM ] 的差异 ( diff )
根据计算的 差异, 更新真实DOM ( patch )
这里牵涉到两个词语 diff 和 patch，稍后再解释，这里简单理解为 ［计算差异］和［应用差异］。
伪代码实现
注：虽然这是这个系列的第一篇，但这已经是第二遍写了。原因是第一遍想完整模拟的时候发现，自己对算法的了解太粗浅，深搜和最短字符算法都不懂，最近和死月大大请教，所以这里偏向思路多一点。
1. 这里我们期望的真实DOM结构是这样的,下面我们一步步实现
<div id="wrap">
<span id="txt">i am some text</span>
</div>
2. 创建虚拟DOM
// 虚拟DOM的构造函数
function VirtualDOM(type,props,children){
this.type = type;
this.props = props || {};
this.children = children || [];
this.rootId = null; // 本节点id
this.mountId = null; // 挂载节点id
}
var textDom = new VirtualDOM('span',{id:'txt'},'i am some text');
var wrapDom = new VirtualDOM('div',{id:'wrap'},[textDom]);
3. 虚拟DOM不能够影响真实DOM，这里我们需要建立连接
最终目的得到这样的字符串，可以供真实DOM使用
"<div v-id="0"><span v-id="0.0">i am some text</span></div>
简单实现 ( 这里需要记录一下每个DOM的id )
var rootIdx = 0; // 标志每一个DOM的唯一id,用'.'区分层级
function mountElement(ele){
ele.rootId = rootIdx++;
var tagOpen = '<' + ele.type + ' v-id="'+ ele.rootId +'">';
var tagClose = '</' + ele.type + '>';
var type;
// 遍历拼凑出虚拟DOM的innerHTML
ele.children.forEach(function(item,index){
item.rootId = ele.rootId + '.' + index; // 区分层级
item.moutId = ele.rootId; // 需要知道挂载在哪个对象上
if(Array.isArray(item.children)){ // 暂且用是否数组判断是否为文本dom
tagOpen += mountElement(item);
}else{
type = item.type;
tagOpen += '<' + type +' v-id="' + item.rootId + '">';
tagOpen += item.children;
tagOpen += '</' +type + '>';
}
});
tagOpen += tagClose;
return tagOpen;
}
var vituralHTML = mountElement(wrapDom);
document.querySelector('#realDom').innerHTML = mountElement(ele);
这里做的事情，就是遍历虚拟DOM，然后拼合虚拟DOM后，以字符串形式输出。
4. 现在我们已经建立了连接了，现在需要模拟一下视图更新，于是我们新生成一个虚拟DOM。
var newtextDom = new VirtualDOM('span',{id:'txt'},'look,i am change!');
var newDom = new VirtualDOM('div',{id:'wrap'},[newtextDom]);
注意:由于React是基于setState的方法去触发视图更新的，但这里要描述的重点是diff，因此我们简单带过。
5. 我们终于进入主题了！我们激动的去比较一下它们的差异
先别激动！
为了更好的描述这个问题，我们这里改变一下上面获取的两个虚拟DOM。
我们打算把结构换成这样的，注意注释的部分，就是两个DOM的不同之处。
<div v-id="0">
<div v-id="0.0">
<span v-id="0.0.0"></span>
<span v-id="0.0.1"></span>
</div>
<div v-id="0.1">
<span v-id="0.1.0"></span>
<span v-id="0.1.1">老的字符</span> // <span v-id="0.1.1">新的字符</span>
</div>
</div>
6. 比较差异
var diffQueue = []; // 记录差异的数组
var diffDepth = 0; // 每下去一层节点就+1
function updateDom(oldDom,newDom){
diffDepth++;
diff(oldDom,newDom,diffQueue);// 比较差异
diffDepth--;
if(diffDepth === 0){
patch(oldDom,diffQueue);
diffQueue = [];
}
}
7. 扁平化
为了方便比较，我们把虚拟DOM，变成Map类型的数据
function flat(children){
var key;
var result = {};
children.forEach(item,index){
key = item.props.key ? item.props.key : index.toString(36);
result[key] = item;
}
return result;
}
8. diff
这里开始我们就正式开始比较了
function diff(oldDom,newDom,diffQueue){
var oldFlat = flat(oldDom.childern);
var newFlat = generateNewMap(oldDom.childern,newDom);
var newIndex = 0; // 作为记录map遍历的顺序
// 遍历新的虚拟DOM
for(key in newFlat){
var oldItem = oldFlat[key];
var newItem = generate[key];
// 差异类型1 ：移动
if(oldItem === newItem){ // 元素完全相同，则认为是顺序移动了
diffQueue.push({
type:UPDATE_TYPES.MOVE,
wrapId:oldItem.mountId, // 之前挂在对象的id
fromIndex:oldItem.rootId, // 本身位置的id
toIndex: nextIndex // 当前遍历的位置
});
} else {
// 差异类型2 ：删除
if(oldItem){ // 旧的和新的不符合，先删除
diffQueue.push({
type:UPDATE_TYPES.REMOVE,
wrapID:oldItem.mountId,
fromIndex:oldItem.rootId,
toIndex:null
});
}
// 差异类型3 ：插入
diffQueue.push({
type:UPDATE_TYPES.INSERT,
wrapId:oldItem.mountId,
fromIndex:null,
toIndex:nextIndex,
ele:newItem // 方便后面渲染出innerHTML
});
}
nextIndex++;
}
// 遍历老的Map，如果新的节点里不存在，也删除掉
for(var key in oldFlat){
var oldItem = oldFlat[key];
var newItem = newFlat[key];
// 差异类型2 ：删除
diffQueue.push({
wrapId: oldItem.mountId,
type: UPATE_TYPES.REMOVE,
fromIndex: oldItem.mountId,
toIndex: null
})
}
}
这里注意到我们生成新的Map是通过 generateNewMap 方法的。 generateNewMap 实际上就是去递归调用diff，完成所有子类的差异比较，最终返回到差异数组。
function generateNewMap(oldChildren,newDom,diffQueue){
newDom.children.forEach(function(newItem,index){
var oldItem = oldChildren[index];
if(shouldUpdate(oldItem,newItem)){
diff(oldItem,newItem,diffQueue);
}
})
}
7. 差异类型
这里简单用整型数字作为纪录
var UPDATE_TYPES = {
MOVE:1, //移动节点
REMOVE:2, // 删除节点
INSERT:3, // 插入节点
TEXT:4 // 节点内容更新
};
8. 应用差异patch
我们已经得到了所有的差异diffQueue，是时候应用这些改动了。
拿插入作例子，我们知道了挂载的对象以及插入的位置，那么我就可以用原生的insertBefore去执行。
function insertAt(target,source,index){
var oldDom = target.children[index]; // 获取目标对象下的的index位置的子元素
source.insertBefore(oldDom);
}
那么通过这些计算得到的source子元素和在目标挂载元素target中的位置index,我们就能够应用这些变化。
下面简单代码再描述一下
function patch(diffQueue){
var deleteArr = [];
var updateSpec = {};
diffQueue.forEach(function(update,index){
if(update.type === UPDATE_TYPES.MOVE || update.type === UPDATE_TYPE.REMOVE){ // 无论是删除还是移动，先存储在删除数组里
var updateIndex = update.fromIndex;
var updateTarget = document.querySelector('[v-id='+updateIndex+']');
var wrapIndex = update.wrapId;
// 保存下来，方便移动使用
updateSpec[wrapIndex] = updateSpec[wrapIndex] || [];
updateSpec[wrapIndex][updateIndex] = updateTarget;
// 记录删除
removeArr.push(updateTarget);
}
// 删除节点
updateTarget.forEach(function(d){
d.remove();
});
// 再次遍历，将移动节点的变化处理掉
diffQueue.forEach(function(update){
var target = document.querySelector(update.wrapId);
switch (update.type) {
case UPATE_TYPES.INSERT_MARKUP:
var source = mountEle(update.ele);
insertChildAt(target, source, update.toIndex);
break;
case UPATE_TYPES.MOVE_EXISTING:
insertChildAt(target, updateSpec[update.wrapId][update.fromIndex], update.toIndex);
break;
});
});
}
10. 大体流程再次回归
diff递归找出不同，存入差异数组。每一个差异元素包含自身位置，父组件位置，差异类型
根据差异类型和差异信息，对旧的虚拟DOM作处理
所有处理结束后，一次性操作真实DOM完成处理
总结
呼…虽然是第二遍写，还是不能很流畅表达，感觉抽象出来的粒度还不够，不过机智的我已经预料到了这一切。
所以第二篇会开始用算法真刀真枪去模拟整个库的形式去解读。每学习到一种解决方案还是很开心的，啦啦啦。
特别推荐
http://purplebamboo.github.io/
博主貌似叫竹隐，文章质量太高了，是那种看完久久不能平复，就算是半夜都想爬起来撸代码，这篇文章就是照撸了一遍，还不够爽，第二遍自己用伪代码撸的。
https://github.com/livoras/blog/issues
抽象能力非常强，加以通俗的语言解释高深的算法，受启发好大
https://github.com/Matt-Esch/virtual-dom
权威的virtual-dom解读，看issues的讨论感觉脑洞真的好大…
http://facebook.github.io/react/docs/reconciliation.html
http://grfia.dlsi.ua.es/ml/algorithms/references/editsurvey_bille.pdf
官方的解读和完整的算法解释( 论文 ) …心目中前端的最终形态
【今日微信公号推荐↓】