DOM-DIFF原理及實(shí)現(xiàn)

面試中如果你簡歷上寫了掌握React属瓣，那面試官肯定會讓你說一下dom-diff算法的過程回挽，
那么今天就實(shí)現(xiàn)一個簡單的dom-diff算法椅文。

虛擬DOM

必須先說一下虛擬DOM的概念饱狂，virtual dom廷没，就是虛擬節(jié)點(diǎn)。是通過js中的Object對象來模擬DOM中的節(jié)點(diǎn)径荔，再通過特定的渲染方法render()將其轉(zhuǎn)化渲染成真實(shí)的DOM節(jié)點(diǎn)督禽。

一個虛擬DOM節(jié)點(diǎn)大概長這樣：
{
type:’節(jié)點(diǎn)類型‘, //ul,div,li,text等等
children:[], //當(dāng)前節(jié)點(diǎn)包含的子節(jié)點(diǎn)集合,內(nèi)部結(jié)構(gòu)也是虛擬DOM節(jié)點(diǎn)組成的數(shù)組
props:{}, //屬性鍵值對

}

//虛擬DOM元素的類：
class Element{
  constructor(type, props, children){
     this.type = type;
     this.props = props;
     this.children = children;
  }
}

那么我們就需要一個方法，創(chuàng)建虛擬DOM節(jié)點(diǎn)总处，并生成這樣結(jié)構(gòu)的對象狈惫；


function createElement(type, props, children){
    return new Element(type, props, children);
}

生成虛擬DOM

我們想在頁面中創(chuàng)建一個ul列表，如下圖所示鹦马，其中包含三個li元素胧谈，每個li中分別包含文本a, b, c，ul,li的屬性分別設(shè)置為class的值為list以及 item, 用上面的方法如何生成虛擬DOM節(jié)點(diǎn)呢?

virualDom01.png

let virtualDom1 = createElement('ul', { class: 'list'}, [
  createElement('li', { class: 'item', ['a']}),
 createElement('li', { class: 'item', ['b']}),
 createElement('li', { class: 'item', ['c']}),
])

代碼參考：生成虛擬DOM節(jié)點(diǎn)

render

render方法實(shí)現(xiàn)的功能是將虛擬DOM轉(zhuǎn)化成真實(shí)DOM荸频，我們可以想到一個方法那就是利用createElement 以及 appendChild菱肖。

/**
* @vnode就是一個Element結(jié)構(gòu)的對象
    {
       type,
       props,
       children,
    }
*/
function render(vnode) {
  //1. 根據(jù)虛擬DOM的節(jié)點(diǎn)類型創(chuàng)建一個該類型的元素
  let element = document.createElement(vnode.type);
  //2. 遍歷其屬性并綁定
  for (let key in vnode.props) {
    //綁定屬性
    setAttr(element, key, vnode.props[key]);
  }
  // .....

  return element;
 }
}

設(shè)置屬性的方法

/*
* node:根據(jù)類型已經(jīng)創(chuàng)建的真實(shí)節(jié)點(diǎn)
* 屬性類型暫時(shí)包含：value值, style樣式，還有其它比如class等旭从。
*/
function setAttr(node, key, value){
   switch(key){
     case 'value':
       let tagName = node.tagName.toUpperCase();
  //如果是文本框或文本區(qū)域則直接將值賦給它的value屬性
       if(/^(INPUT|TEXTAREA)$/.test(tagName)){
         node.value = value;
       }else {
         node.setAttribute(key, value);
       }
       break;
       
     case 'style':
       //如果是內(nèi)聯(lián)樣式屬性則賦值給node.style.cssText屬性
       node.style.cssText = value;
       
       break;
       
     default:
       node.setAttribute(key, value);
       break;
   }
}

接下來就是對vnode的children子節(jié)點(diǎn)的渲染稳强，我們知道一個思路，如果子節(jié)點(diǎn)仍然是Element類型和悦，即虛擬DOM元素退疫，則需要繼續(xù)進(jìn)行遞歸render轉(zhuǎn)化,于是在render方法中還需要：

//3. 遍歷children子元素
(vnode.children || []).forEach(child =>{
  child = (child instanceof Element)? render(child): document.createTextNode(child);
  element.appendChild(child);

})

最后轉(zhuǎn)換成為真實(shí)DOM的節(jié)點(diǎn)還差一步就可以渲染到頁面中：

//渲染節(jié)點(diǎn), 將虛擬dom渲染成真實(shí)DOM
function renderDOM(elements, target){
    target.appendChild(elements);
}

參考代碼：render

DOM-DIFF

DOM-DIFF就是一種比較算法,比較兩個虛擬DOM的區(qū)別，也就是比較兩個對象的區(qū)別鸽素。
也有真實(shí)DOM與虛擬DOM的比較蹄咖，不過我們這里先只討論虛擬DOM之間的比較。

DOM-DIFF的過程

DOM-DIFF作用是通過js層面的計(jì)算付鹿，根據(jù)兩個虛擬對象創(chuàng)建出差異的補(bǔ)丁對象patch澜汤，用來描述改變了哪些內(nèi)容，然后用特定的操作解析patch對象舵匾，更新dom完成頁面的重新渲染俊抵。
那我們按照下圖的變更來實(shí)現(xiàn)一個DOM-diff的過程：

圖2-diff新舊樹對比.png

DOM-DIFF三種優(yōu)化策略

只比較平級

規(guī)則一：只比較平級
不會跨級比較

規(guī)則二：不跨級
同一級的變化節(jié)點(diǎn)，如果節(jié)點(diǎn)相同只是位置交換坐梯，則會復(fù)用徽诲。

規(guī)則三：同級易位可復(fù)用

PS:通過key來實(shí)現(xiàn)。

差異計(jì)算

先序深度優(yōu)先遍歷

遍歷次序深度優(yōu)先遍歷.png
JS對象模擬并生成虛擬DOM
將虛擬DOM轉(zhuǎn)成真實(shí)DOM并插入到頁面中
若事件觸發(fā)了虛擬DOM的變更吵血，則比較兩棵虛擬DOM樹的差異谎替，得到差異對象patch
把差異對象patch應(yīng)用到真實(shí)的DOM樹中渲染。

差異對象patch

/*
* 遞歸樹蹋辅，比較后的結(jié)果放到補(bǔ)丁包中
*  * 規(guī)則：
 * 1. 結(jié)點(diǎn)類型type相同時(shí)钱贯，則看props是否相同。產(chǎn)生一個屬性補(bǔ)丁包{ type:'ATTRS',attrs:{ class: 'list-group'}}
 * 2. 新dom結(jié)點(diǎn)不存在的情況侦另，   { type:' REMOVE', index:xxx }
 * 3. 結(jié)點(diǎn)類型不相同秩命，直接替換, { type:'REPLACE', newNode: newNode}
 * 4. 文本的變化，            { type:'TEXT', text: 1}
   
*/

//生成補(bǔ)丁包
 function generate(oldNode, newNode, index, patches){
 //每個元素都有補(bǔ)丁對象
   let currentPatch = [];
   //規(guī)則2：新節(jié)點(diǎn)不存在的情況
   if(!newNode){
     currentPatch.push({type:'REMOVE', index});
   } else if(diffToos.isString(oldNode) && diffTools.isString(newNode)){
     //規(guī)則4：文本節(jié)點(diǎn)變化
    currentPatch.push({ type: 'TEXT', text:newNode});
   } else if(newNode.type === oldNode.type){
     //規(guī)則1：節(jié)點(diǎn)類型相同褒傅，比較屬性
     let attrs = diffTools.attrs(oldNode.props, newNode.props);
     //獲取到的差異屬性放到當(dāng)前節(jié)點(diǎn)的補(bǔ)丁包中
     if(Object.keys(attrs).length >0){
       currentPatch.push({type:'ATTRS', attrs});
     }
     //若有子節(jié)點(diǎn)弃锐，則繼續(xù)比較
     diffTools.child(oldNode.children, newNode.children, index, patches);
     
   }else {//規(guī)則3： 節(jié)點(diǎn)類型不相同，直接替換
     currentPatch.push({type:'REPLACE', newNode});
     
   }
   
   //TODO 如果平級元素互換殿托，會導(dǎo)致重新渲染霹菊，其實(shí)移動一下就可以
   //TODO 新增節(jié)點(diǎn)也不會被更新
   
   //最后如果當(dāng)前節(jié)點(diǎn)的補(bǔ)丁包中有內(nèi)容,則將其放入整棵樹的補(bǔ)丁包中
   if(currentPatch.length){
     patches[index] = currentPatch;
   }
  
  }

打補(bǔ)丁時(shí)需要的工具集

/*
* 一些比較時(shí)用到的工具
*/
let Index = 0;
let diffTools = {
  //判斷節(jié)點(diǎn)是否為文本節(jié)點(diǎn)
  isString(node){
    return Object.prototype.toString.call(node) == '[object String]';
  },
  //比較新舊屬性差異，并返回最終要修改的屬性
  attrs(oldProps, newProps){
    let patch = {};
    //依次遍歷新舊節(jié)點(diǎn)屬性
    for(let key in oldProps){
      //1. 若舊屬性與新屬性不同或者在新屬性中不存在支竹，即為刪除或變更
      patch[key] = newProps[key]; //則以新的為準(zhǔn)旋廷；
      
    }
    
    for(let key in newProps){
      //1. 若新屬性在舊屬性中不存在，即為追加
      if(!oldProps.hasOwnProperty(key)){
        patch[key] = newProps[key]; //也以新的為準(zhǔn)
      }
    }
    return patch;
  },
  //繼續(xù)比較子節(jié)點(diǎn)
  child(oldChild,newChild, index, patches){
    oldChild.forEach((child, idx)=>{
      //每一層比較唾戚，使用同一Index,所以用全局的Index
      generate(child, newChild[idx], ++Index, patches);
    })
  }
}

比較方法

維護(hù)兩樹不同的補(bǔ)丁包

function diff(oldTree, newTree){
  //兩樹的差異補(bǔ)丁包
  let patches = {};
  
  let index = 0; //默認(rèn)從第0個節(jié)點(diǎn)開始比較
  generate(oldTree, newTree, index, patches);
  
  return patches;
  
}

最后模擬兩棵不同的樹結(jié)構(gòu)柳洋，并打印出補(bǔ)丁包

let virtualDom1 = createElement('ul', { class: 'list'}, [
    createElement('li',{class:'item'}, ['a']),
    createElement('li',{class:'item'}, ['b']),
    createElement('li',{class:'item'}, ['c'])
]);
let virtualDom2= createElement('ul', { class: 'list'}, [
    createElement('li',{class:'item'}, ['1']),
    createElement('li',{class:'item-active'}, ['b']),
    createElement('div',{class:'item-div'}, ['3']),
    
]);
let el = render(virtualDom1);
let patches = diff(virtualDom1, virtualDom2);
console.log('打印出補(bǔ)丁包’, patches);
renderDOM(el, window.root);

代碼參考：diff比較生成差異補(bǔ)丁包

打補(bǔ)丁

現(xiàn)在還差一步，就是打補(bǔ)丁

//打補(bǔ)丁規(guī)則
function doPatch(node, patches){
  patches.forEach(patch =>{
    //補(bǔ)丁根據(jù)類型叹坦，ATTRS,TEXT,REPLACE,REMOVE
    switch(patch.type){
      case 'ATTRS':
        for(let key in patch.attrs){
          let value = patch.attrs[key];
          if(value){
            setAttr(node, key,value);
          }else {
            node.removeAttribute(key);
          }
        }
        break;
      case 'TEXT':
        node.textContent = patch.text;
        break;
      case 'REPLACE':
        let newNode = (patch.newNode instanceof Element)?
            render(patch.newNode): document.createTextNode(patch.newNode);
        //用新節(jié)點(diǎn)替換
        node.parentNode.replaceChild(newNode, node)
        break;
      case 'REMOVE':
        node.parentNode.removeChild(newNode, node)
        break;
      default:
        break;
        
    }
  })
  
}

現(xiàn)在就是依次遍歷需要變更的元素并執(zhí)行打補(bǔ)丁的操作

//依次打補(bǔ)丁
let patchIndex = 0;
function patch(node, patches){
  let currentPatch = patches[patchIndex ++]
  let childNodes = node.childNodes;
  
  childNodes.forEach(child=>{
    patch(child, patches);
  });
  
  if(currentPatch){
    doPatch(node, currentPatch);
  }
}

把補(bǔ)丁包給目標(biāo)元素打上熊镣，并更新視圖：

patch(el, patches);

代碼參考：打補(bǔ)丁

簡易版的DOM-diff就到這里，目前還有一些關(guān)于key的優(yōu)化以及同級元素易位只需替換的邏輯還未實(shí)現(xiàn)募书。
等下一篇再深入去實(shí)現(xiàn)并練習(xí)绪囱。