转载

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

前言：

读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 = [];     }        }

6. 扁平化

为了方便比较，我们把虚拟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. 大体流程再次回归