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

面試中如果你簡(jiǎn)歷上寫(xiě)了掌握React，那面試官肯定會(huì)讓你說(shuō)一下dom-diff算法的過(guò)程，
那么今天就實(shí)現(xiàn)一個(gè)簡(jiǎn)單的dom-diff算法。

虛擬DOM

必須先說(shuō)一下虛擬DOM的概念，virtual dom，就是虛擬節(jié)點(diǎn)。是通過(guò)js中的Object對(duì)象來(lái)模擬DOM中的節(jié)點(diǎn)，再通過(guò)特定的渲染方法render()將其轉(zhuǎn)化渲染成真實(shí)的DOM節(jié)點(diǎn)。

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

}

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

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


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

生成虛擬DOM

我們想在頁(yè)面中創(chuàng)建一個(gè)ul列表，如下圖所示，其中包含三個(gè)li元素，每個(gè)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，我們可以想到一個(gè)方法那就是利用createElement 以及 appendChild。

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

  return element;
 }
}

設(shè)置屬性的方法

/*
* node:根據(jù)類(lèi)型已經(jīng)創(chuàng)建的真實(shí)節(jié)點(diǎn)
* 屬性類(lèi)型暫時(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;
   }
}

接下來(lái)就是對(duì)vnode的children子節(jié)點(diǎn)的渲染，我們知道一個(gè)思路，如果子節(jié)點(diǎn)仍然是Element類(lèi)型，即虛擬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)還差一步就可以渲染到頁(yè)面中：

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

參考代碼：render

DOM-DIFF

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

DOM-DIFF的過(guò)程

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


圖2-diff新舊樹(shù)對(duì)比.png

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

  1. 只比較平級(jí)


    規(guī)則一：只比較平級(jí)

  2. 不會(huì)跨級(jí)比較


    規(guī)則二：不跨級(jí)

  3. 同一級(jí)的變化節(jié)點(diǎn)，如果節(jié)點(diǎn)相同只是位置交換，則會(huì)復(fù)用。


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

    PS:通過(guò)key來(lái)實(shí)現(xiàn)。

差異計(jì)算

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


    遍歷次序深度優(yōu)先遍歷.png
  2. JS對(duì)象模擬并生成虛擬DOM
  3. 將虛擬DOM轉(zhuǎn)成真實(shí)DOM并插入到頁(yè)面中
  4. 若事件觸發(fā)了虛擬DOM的變更，則比較兩棵虛擬DOM樹(shù)的差異，得到差異對(duì)象patch
  5. 把差異對(duì)象patch應(yīng)用到真實(shí)的DOM樹(shù)中渲染。
差異對(duì)象patch
/*
* 遞歸樹(shù)，比較后的結(jié)果放到補(bǔ)丁包中
*  * 規(guī)則：
 * 1. 結(jié)點(diǎn)類(lèi)型type相同時(shí)，則看props是否相同。產(chǎn)生一個(gè)屬性補(bǔ)丁包{ type:'ATTRS',attrs:{ class: 'list-group'}}
 * 2. 新dom結(jié)點(diǎn)不存在的情況，   { type:' REMOVE', index:xxx }
 * 3. 結(jié)點(diǎn)類(lèi)型不相同，直接替換, { type:'REPLACE', newNode: newNode}
 * 4. 文本的變化，            { type:'TEXT', text: 1}
   
*/

//生成補(bǔ)丁包
 function generate(oldNode, newNode, index, patches){
 //每個(gè)元素都有補(bǔ)丁對(duì)象
   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)類(lèi)型相同，比較屬性
     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)類(lèi)型不相同，直接替換
     currentPatch.push({type:'REPLACE', newNode});
     
   }
   
   //TODO 如果平級(jí)元素互換，會(huì)導(dǎo)致重新渲染，其實(shí)移動(dòng)一下就可以
   //TODO 新增節(jié)點(diǎn)也不會(huì)被更新
   
   //最后如果當(dāng)前節(jié)點(diǎn)的補(bǔ)丁包中有內(nèi)容,則將其放入整棵樹(shù)的補(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ù)兩樹(shù)不同的補(bǔ)丁包

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

最后模擬兩棵不同的樹(shù)結(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ù)類(lèi)型，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ǔ)丁

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容