微信号:FrontDev

介绍:分享 Web 前端相关的技术文章、工具资源、精选课程、热点资讯

Vitural Dom & diff算法 (一) 伪代码实现

2016-01-03 21:03 前端大全

(点击上方,可快速关注)


作者:大搜车前端团队博客

网址: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>


流程


  1. 创建虚拟DOM

  2. 真实DOM 连接 虚拟DOM

  3. 视图更新

  4. 计算 [ 新虚拟DOM ] 和 [ 旧虚拟DOM ] 的差异 ( diff )

  5. 根据计算的 差异, 更新真实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

官方的解读和完整的算法解释( 论文 ) …心目中前端的最终形态



【今日微信公号推荐↓】

 
前端大全 更多文章 5个典型的JavaScript面试题(上) Limu:JavaScript的那些书 Web开发:我希望得到的编程学习路线图 JavaScript基础工具清单 常用排序算法之JavaScript实现
猜您喜欢 「非著名程序员」周报第二期 SuperWebView进驻Android Studio中文社区 Python标准库10 多进程初步 (multiprocessing包) 埋点进化论:从埋点到无埋点 Introducing Android Instant Apps