javascript基础修炼(11)——DOM-DIFF的实现

参考代码将上传至我的github仓库，欢迎互粉：https://github.com/dashnowords/blogs/tree/master

一. 再谈从Virtual-Dom生成真实DOM
二. DOM-Diff的目的
三. DOM-Diff的基本算法描述
四. DOM-Diff的简单实现

一. 再谈从Virtual-Dom生成真实DOM

在上一篇博文《javascript基础修炼(10)——VirtualDOM和基本DFS》中第三节演示了关于如何利用Virtual-DOM的树结构生成真实DOM的部分，原本希望让不熟悉深度优先算遍历的读者先关注和感受一下遍历的基本流程，所以演示用的DOM节点只包含了类名和文本内容，结构简单，在复现DOM结构时直接拼接字符串在控制台显示出来的方式。许多读者留言表示对如何从Virtual-Dom得到真实的DOM节点仍然很困惑。

所以本节会先为Element类增加渲染方法，演示如何将Virtual-Dom转换为真正的DOM节点并渲染在页面上。

element.js示例代码：

//Virtual-DOM 节点类定义

class Element{

    /**

   * @param {String} tag 'div' 标签名

   * @param {Object} props { class: 'item' } 属性集

   * @param {Array} children [ Element1, 'text'] 子元素集

   * @param {String} key option

   */

  constructor(tag, props, children, key) {

     this.tag = tag;

     this.props = props;

     if (Array.isArray(children)) {

        this.children = children;

     } else if (typeof children === 'string'){

        this.children = null;

        this.key = children;

     }

     if (key) {this.key = key};

  }

  /**

   * 从虚拟DOM生成真实DOM

   * @return {[type]} [description]

   */

  render(){

     //生成标签

     let el = document.createElement(this.tag);

     let props = this.props;

     //添加属性

     for(let attr of Object.keys(props)){

        el.setAttribute(attr, props[attr]);

     }

     //处理子元素

     var children = this.children || [];

     children.forEach(function (child) {

         var childEl = (child instanceof Element)

         ? child.render()//如果子节点是元素，则递归构建

         : document.createTextNode(child);//如果是文本则生成文本节点

         el.appendChild(childEl);

     });

     //将DOM节点的引用挂载至对象上用于后续更新DOM

     this.el = el;

     //返回生成的真实DOM节点

     return el;

  }

}

//提供一个简写的工厂函数

function h(tag, props, children, key) {

    return new Element(tag, props, children, key);

}

测试一下定义的Element类：

var app = document.getElementById('anchor');

var tree = h('div',{class:'main', id:'body'},[

       h('div',{class:'sideBar'},[

          h('ul',{class:'sideBarContainer',cprop:1},[

               h('li',{class:'sideBarItem'},['page1']),

               h('li',{class:'sideBarItem'},['page2']),

               h('li',{class:'sideBarItem'},['page3']),

            ])

        ]),

       h('div',{class:'mainContent'},[

           h('div',{class:'header'},['header zone']),

           h('div',{class:'coreContent'},[

                 h('div',{fx:1},['flex1']),

                 h('div',{fx:2},['flex2'])

            ]),

           h('div',{class:'footer'},['footer zone']),

        ])

    ]);

//生成离线DOM

var realDOM = tree.render();

//挂载DOM

app.appendChild(realDOM);

这次不用再看控制台了，虚拟DOM的内容已经变成真实的DOM节点渲染在页面上了。

接下来，就正式进入通过DOM-Diff来检测Virtual-DOM的变化以及更新视图的后续步骤。

二. DOM-Diff的目的

在经历了一些操作或其他影响后，Virtual-DOM上的一些节点发生了变化，此时页面上的真实DOM节点是与旧的DOM树保持一致的（因为旧的DOM树就是依据旧的Virtual-DOM来渲染的），DOM-Diff所实现的功能就是找出新旧两棵Virtual-DOM之间的区别，并将这些变更渲染到真实的DOM节点上去。

三. DOM-Diff的基本算法描述

为了提升效率，需要在算法中使用基本的“批处理”思维，也就是说，先通过遍历Virtual-DOM找出所有节点的差异，将其记录在一个补丁包patches中，遍历结束后再根据补丁包一并执行addPatch()逻辑来更新视图。完整的树比较算法时间复杂度过高，DOM-Diff中使用的算法是只对新旧两棵树中的节点进行同层比较，忽略跨层比较。

历，并为每个节点添加索引

新旧节点的tagName或者key不同

表示旧的节点需要被替换，其子节点也就不需要遍历了，这种情况的处理比较简单粗暴，打补丁阶段会直接把整个旧节点替换成新节点。
新旧节点tagName和key相同

开始检查属性：
- 检查属性删除的情况
- 检查属性修改的情况
- 检查属性新增的情况
- 将变更以属性变更的类型标记加入patches补丁包中
完成比较后根据patches补丁包将Virtual-DOM的变化渲染到真实DOM节点。

四. DOM-Diff的简单实现

4.1 期望效果

我们先来构建两棵有差异的Virtual-DOM,模拟虚拟DOM的状态变更:

<!--旧DOM树-->

<div class="main" id="body">

  <div class="sideBar">

     <ul class="sideBarContainer" cprop="1">

         <li class="sideBarItem">page1</li>

         <li class="sideBarItem">page2</li>

         <li class="sideBarItem">page3</li>

     </ul>

  </div>

  <div class="mainContent">

      <div class="header">header zone</div>

      <div class="coreContent">

           <div fx="1">flex1</div>

           <div fx="2">flex2</div>

      </div>

      <div class="footer">footer zone</div>

  </div>

</div>

<!--新DOM树-->

<div class="main" id="body">

  <div class="sideBar">

     <ul class="sideBarContainer" cprop="1" ap='test'>

         <li class="sideBarItem" bp="test">page4</li>

         <li class="sideBarItem">page5</li>

         <div class="sideBarItem">FromLiToDiv</div>

     </ul>

  </div>

  <div class="mainContent">

      <div class="header">header zone</div>

      <div class="coreContent">

           <div fx="3">flex1</div>

           <div fx="2">flex2</div>

      </div>

      <div class="footer">footer zone</div>

  </div>

</div>

如果DOM-Diff算法正常工作，应该会检测出如下的区别:

1.ul标签上增加ap="test"属性

2.li第1个标签修改了文本节点内容并增加了新属性

3.第2个节点修改了内容

4.li第3个元素替换为div元素

5.flex1所在标签的fx属性值发生了变化

/*由于深度优先遍历时会按访问次序对节点增加索引代号，所以上述变化会相应转变为类似于如下标记形式*/

patches = {

    '2':[{type:'新增属性',propName:'ap',value:'test'}],

    '3':[{type:'新增属性',propName:'bp',value:'test'},{type:'修改内容',value:'page4'}],

    '4':[{type:'修改内容',value:'page5'}],

    '5':[{type:'替换元素',node:{tag:'div',.....}}]

    '9':[{type:'修改属性',propName:'fx',value:'3'}]

}

4.2 DOM-Diff代码

代码简化了判断逻辑所以不是很长，就直接写在一起实现了，方便学习，细节部分直接以注释形式写在代码中。

省略的逻辑部分主要是针对例如多个li等列表形式元素的，不仅包含标签本身的增删改，还涉及排序和元素追踪，场景较为复杂，会在后续博文中专门描述。

domdiff.js:

/**

 * DOM-Diff主框架

 */

/**

 * #define定义补丁的类型

 */

let PatchType = {

    ChangeProps: 'ChangeProps',

    ChangeInnerText: 'ChangeInnerText',

    Replace: 'Replace'

}

function domdiff(oldTree, newTree) {

   let patches = {}; //用于记录差异的补丁包

   let globalIndex = 0; //遍历时为节点添加索引，方便打补丁时找到节点

   dfsWalk(oldTree, newTree, globalIndex, patches);//patches会以传址的形式进行递归，所以不需要返回值

   console.log(patches);

   return patches;

}

//深度优先遍历树

function dfsWalk(oldNode, newNode, index, patches) {

    let curPatch = [];

    let nextIndex = index + 1;

    if (!newNode) {

        //如果没有传入新节点则什么都不做

    }else if (newNode.tag === oldNode.tag && newNode.key === oldNode.key){

        //节点相同，开始判断属性(未写key时都是undefined，也是相等的)

        let props = diffProps(oldNode.props, newNode.props);

        if (props.length) {

            curPatch.push({type : PatchType.ChangeProps, props});

        }

        //如果有子树则遍历子树

        if (oldNode.children.length>0) {

            if (oldNode.children[0] instanceof Element) {

                //如果是子节点就递归处理

                nextIndex = diffChildren(oldNode.children, newNode.children, nextIndex, patches);

            } else{

                //否则就当做文本节点对比值

                if (newNode.children[0] !== oldNode.children[0]) {

                    curPatch.push({type : PatchType.ChangeInnerText, value:newNode.children[0]})

                }

            }

        }

    }else{

        //节点tagName或key不同

        curPatch.push({type : PatchType.Replace, node: newNode});

    }

    //将收集的变化添加至补丁包

    if (curPatch.length) {

        if (patches[index]) {

            patches[index] = patches[index].concat(curPatch);

        }else{

            patches[index] = curPatch;

        }

    }

    //为追踪节点索引，需要将索引返回出去

    return nextIndex;

}

//对比节点属性

/**

 * 1.遍历旧序列，检查是否存在属性删除或修改

 * 2.遍历新序列，检查属性新增

 * 3.定义：type = DEL 删除

 *         type = MOD 修改

 *         type = NEW 新增

 */

function diffProps(oldProps, newProps) {

    let propPatch = [];

    //遍历旧属性检查删除和修改

    for(let prop of Object.keys(oldProps)){

        //如果是节点删除

       if (newProps[prop] === undefined) {

          propPatch.push({

              type:'DEL',

              propName:prop

          });

       }else{

         //节点存在则判断是否有变更

         if (newProps[prop] !== oldProps[prop]) {

            propPatch.push({

                type:'MOD',

                propName:prop,

                value:newProps[prop]

            });

         }

       }

    }

    //遍历新属性检查新增属性

    for(let prop of Object.keys(newProps)){

        if (oldProps[prop] === undefined) {

            propPatch.push({

                type:'NEW',

                propName:prop,

                value:newProps[prop]

            })

        }

    }

    //返回属性检查的补丁包

    return propPatch;

}

/**

 * 遍历子节点

 */

function diffChildren(oldChildren,newChildren,index,patches) {

    for(let i = 0; i < oldChildren.length; i++){

        index = dfsWalk(oldChildren[i],newChildren[i],index,patches);

    }

    return index;

}

运行domdiff( )来对比两棵树查看结果：

可以看到与我们期望的结果时一致的。

4.3 根据补丁包更新视图

拿到补丁包后，就可以更新视图了，更新视图的算法逻辑如下：

再次深度优先遍历Virtual-DOM,如果遇到有补丁的节点就调用changeDOM( )方法来修改页面，否则增加索引继续搜索。

addPatch.js:

/**

 * 根据补丁包更新视图

 */

function addPatch(oldTree, patches) {

   let globalIndex = 0; //遍历时为节点添加索引，方便打补丁时找到节点

   dfsPatch(oldTree, patches, globalIndex);//patches会以传址的形式进行递归，所以不需要返回值

}

//深度遍历节点打补丁

function dfsPatch(oldNode, patches, index) {

    let nextIndex = index + 1;

    //如果有补丁则打补丁

    if (patches[index] !== undefined) {

        //刷新当前虚拟节点对应的DOM

        changeDOM(oldNode.el,patches[index]);

    }

    //如果有自子节点且子节点是Element实例则递归遍历

    if (oldNode.children.length && oldNode.children[0] instanceof Element) {

        for(let i =0 ; i< oldNode.children.length; i++){

           nextIndex = dfsPatch(oldNode.children[i], patches, nextIndex);

        }

    }

    return nextIndex;

}

//依据补丁类型修改DOM

function changeDOM(el, patches) {

    patches.forEach(function (patch, index) {

        switch(patch.type){

            //改变属性

            case 'ChangeProps':

               patch.props.forEach(function (prop, index) {

                   switch(prop.type){

                      case 'NEW':

                      case 'MOD':

                          el.setAttribute(prop.propName, prop.value);

                      break;

                      case 'DEL':

                          el.removeAttribute(prop.propName);

                      break;

                   }

               })

            break;

            //改变文本节点内容

            case 'ChangeInnerText':

                 el.innerHTML = patch.value;

            break;

            //替换DOM节点

            case 'Replace':

                let newel = h(patch.node.tag, patch.node.props, patch.node.children).render();

                el.parentNode.replaceChild(newel , el);

        }

    })

}

在页面测试按钮的事件监听函数中，DOM-Diff执行后，再调用addPatch( )即可看到，新的DOM树已经被渲染至页面了：

小结

DomDiff算法思想其实并不是特别难理解，自己手写代码时主要的难点出现在节点索引的追踪上，因为在addPatch( )阶段，需要将补丁包中的节点索引编号与旧的Virtual-DOM树对应起来，这里涉及的基础知识点有两个：

函数形参为对象类型时是传入对象引用的，在函数中修改对象属性是会影响到函数外部作用域的，而patches补丁包正是利用了这个基本特性，从顶层向下传递在最外层生成的patches对象引用，深度优先遍历时用于递归的函数有一个形参表示patches，这样在遍历时，无论遍历到哪一层，都是共享同一个patches的。
第二个难点在于节点索引追踪，比如第二层有3个节点，第一个被标号为2,同层第二个节点的编号取决于第一个节点的子节点消耗了多少个编号，所以代码中在dfswalk( )迭代函数中return了一个编号，向父级调用者传递的信息是：我和我所有的子级节点都已经遍历完了，最后一个节点（或者下一个可使用节点）的索引是XXX，这样遍历函数能够正确地标记和追踪节点的索引了，觉得这一部分不太好理解的读者可以自己手画一下深度优先遍历的过程就比较容易理解了。
本篇中在节点的比较策略上只列举了一些基本场景，列表相关的节点对比相对复杂，在以后的博文中再展开描述。

巴特西