javascript基礎修煉(11)——DOM-DIFF的實現

參考代碼將上傳至我的倉庫，歡迎互粉： "https://github.com/dashnowords/blogs/tree/master" [TOC] 一. 再談從Virtual Dom生成真實DOM 在上一篇博文 "《javascript基礎修煉(10)——VirtualDOM和基本DFS》" ...

一. 再談從Virtual-Dom生成真實DOM
二. DOM-Diff的目的
三. DOM-Diff的基本演算法描述
四. DOM-Diff的簡單實現

參考代碼將上傳至我的github倉庫，歡迎互粉：https://github.com/dashnowords/blogs/tree/master

一. 再談從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，這樣遍歷函數能夠正確地標記和追蹤節點的索引了，覺得這一部分不太好理解的讀者可以自己手畫一下深度優先遍歷的過程就比較容易理解了。
本篇中在節點的比較策略上只列舉了一些基本場景，列表相關的節點對比相對複雜，在以後的博文中再展開描述。