首先我们需要将 DOM 树上的结构, 属性信息我们都可以很容易地用 JavaScript 对象表示出来:
javascript 代码
- var element={
- tagName:'ul',
- props:{
- id:'list'
- },
- children:[ {tagName:'li',props:{class:'item'},child:["Item 1"]},
- {tagName:'li',props:{class:'item'},child:["Item 2"]},
- {tagName:'li',props:{class:'item'},child:["Item 3"]}
- ]
- }
html 代码
<ul id='list'>
<li class='item'>Item 1</li>
<li class='item'>Item 2</li>
<li class='item'>Item 3</li>
</ul>
下面正式介绍一下 Virtual DOM 算法, 包括几个步骤
1. 用 JavaScript 对象结构表示 DOM 树的结构; 然后用这个树构建一个真正的 DOM 树, 插到文档当中
2. 当状态变更的时候, 重新构造一棵新的对象树. 然后用新的树和旧的树进行比较, 记录两棵树差异
3. 把 2 所记录的差异应用到步骤 1 所构建的真正的 DOM 树上, 视图就更新了
Virtual DOM 本质上就是在 JS 和 DOM 之间做了一个缓存.#####
算法实现
步骤一: 用 JS 对象模拟 DOM 树
javascript 代码
- function Element(tagName,props,children){
- this.tagName=tagName;
- this.props=props;
- this.children=children;
- }
- module.export=function(tagName,props,chileren){
- return new Element(tagName,props,children);
- }
例如上面的 DOM 结构就可以简单的表示:
javascript 代码
- var el=require('./element');
- var ul=el('ul',{id:'list'},[
- el('li',{class:'item'},['Item 1']),
- el('li',{class:'item'},['Item 2']),
- el('li',{class:'item'},['Item 3'])
- ]);
现在 ul 只是一个 JavaScript 对象表示的 DOM 结构, 页面上并没有这个结构. 我们可以根据这个 ul 构建真正的 < ul>:
javascript 代码
- Element.prototype.render=function(){
- var el=document.createElement(this.tagName);
- var props=this.props;
- for(var propName in props){
- var propValue=props[propName];
- el.setAttribute(propName,propValue);
- }
- var children=this.children||[];
- children.forEach(function(child){
- var childEl=(child instanceof Element)?child.render():document.createTextNode(child);
- el.append(childEl);
- })
- return el;
- }
render 方法会根据 tagName 构建一个真正的 DOM 节点, 然后设置这个节点的属性, 最后递归地把自己的子节点也构建起来. 所以只需要:
javascript 代码
- var ulRoot=ul.render();
- document.body.appendChild(ulRoot);
步骤二: 比较两棵虚拟 DOM 树的差异 (Virtual DOM diff)
(1) 深度优先遍历, 记录差异
在实际的代码中, 会对新旧两棵树进行一个深度优先的遍历, 这样每个节点都会有一个唯一的标记;
在深度优先遍历的时候, 每遍历到一个节点就把该节点和新的的树进行对比. 如果有差异的话就记录到一个对象里面.
javascript 代码
- function diff(oldTree,newTree){
- var index=0;// 当前节点的标志
- var patches={}// 用来记录每个节点差异的对象
- dfsWalk(oldTree,newTree,index patches);
- return patches;
- }
- function dfsWalk(oldNode,newNode,index,patches){
- // 对比 oldNode 和 newNode 的不同, 记录下来
- patches[index] = [...];
- diffChildren(oldNode,.children,newNode.children,index,patches);
- }
- function diffChildren(oldChildren,newChildren,index,patches){
- var leftNode=null;
- var currentNodeIndex=index;
- oldChildren.forEach(function(child,i){
- var newChild=newChildren[i];
- currentNodeIndex=(leftNode&&leftNode.count)?currentNodeIndex+leftNode.count+1:currentNodeIndex+1;
- dfsWalk(child,newChild,currentNodeIndex,patches);
- leftNode=child;
- })
- }
(2) 差异类型
节点的差异指的是什么呢? 对 DOM 操作可能会:
a. 替换掉原来的节点, 例如把上面的 div 换成了 section;==>var REPLACE = 0
b. 移动, 删除, 新增子节点, 例如上面 div 的子节点, 把 p 和 ul 顺序互换;==>var REORDER = 1
c. 修改了节点的属性;==>var PROPS = 2
d. 对于文本节点, 文本内容可能会改变. 例如修改上面的文本节点 2 内容为 Virtual DOM 2.==>var TEXT = 3
如 div 换成 section, 如果给 div 新增了属性 id 为 container, 如果是文本节点, 如上面的文本节点 2, 就记录下:
javascript 代码
- patches[0]=[{
- type:REPLACE,
- node:newNode,//el('section',props,children)
- },{
- type:PROPS,
- props:{
- id:'container'
- }
- },{
- type: TEXT,
- content: "Virtual DOM2"
- }]
(3) 列表对比算法
现在知道了新旧的顺序, 求最小的插入, 删除操作 (移动可以看成是删除和插入操作的结合). 这个问题抽象出来其实是字符串的最小编辑距离问题 (Edition Distance),
常见的解决算法是 Levenshtein Distance, 通过动态规划求解, 时间复杂度为 O(M * N). 但是我们并不需要真的达到最小的操作, 我们只需要优化一些比较常见的移动情况,
牺牲一定 DOM 操作, 让算法时间复杂度达到线性的 (O(max(M, N)).
步骤三: 把差异应用到真正的 DOM 树上
javascript 代码
- function path(node,patches){
- var walker={index:0};
- dfsWalker(node,walker,patches);
- }
- function dfsWalker(node,walker,patches){
- var currentPathes=patches[walker.index];
- var len=node.childNodes?node.childNodes.length:0;
- for(var i=0;i<len;i++){
- var child=node.childNodes[i];
- walker.index++;
- dfsWalker(chid,walker,patches);
- }
- if(currentPathes){
- applyPathes(node,currentPathes);
- }
- }
- function applyPatches(node,currentPathes){
- currentPathes.forEach(function(currentPath){
- switch(currentPath.type){
- case REPLACE:
- node.parentNode.replaceChild(currentPath.node.render(),node);
- break;
- case REORDER:
- reorderChildren(node,currentPath.moves);
- break;
- case PROPS:
- setProps(node,currentPath.props);
- break;
- case TEXT:
- node.textContent=currentPath.content;
- default:
- throw new Error('Unkown path type'+currentPath.type);
- }
- })
- }
如果想深入理解算法, 可以参考 https://github.com/livoras/simple-virtual-dom 上的工程
来源: http://www.qdfuns.com/article/24440/0274a270b58498293e0fc0238253d9bd.html