「源碼剖析」如何實現一個虛擬DOM算法

作者：小丑 2021-01-28 07:21:13

我們希望是在更新的時候通過新渲染的虛擬DOM樹和舊的虛擬DOM樹進行對比,記錄這兩顆樹的差異。記錄下來的不同就是我們需要對頁面真正的DOM操作，然后把它們渲染在真正的DOM結構上，頁面就對應的變化了。

上篇文章《虛擬DOM如何進化為真實DOM》中講到了如何通過虛擬DOM樹轉化為真實DOM渲染到頁面中。但是在渲染的過程中，我們直接將新的虛擬DOM樹轉化成真實DOM替換掉舊的DOM結構。當真實的DOM中的狀態或者內容發生變化的時候，重新渲染新的虛擬DOM樹再替換掉舊的，這樣的話會顯得很無力。設想一種情景，當我們對整個DOM結構中只是修改了一個小的數據甚至是一個標點符號的時候或者數據量很大的時候，我們要把原來舊的DOM結構全部替換掉，這樣的話對計算機而言太浪費性能了。

故我們希望是在更新的時候通過新渲染的虛擬DOM樹和舊的虛擬DOM樹進行對比,記錄這兩顆樹的差異。記錄下來的不同就是我們需要對頁面真正的DOM操作，然后把它們渲染在真正的DOM結構上，頁面就對應的變化了。這樣就實現了：看似視圖全部結構得到了最新的渲染,但是最后操作DOM結構的時候只是改變了與原結構不同的地方。

即虛擬DOM的diff算法的主體思路是：

1.將虛擬DOM結構轉化為真實的DOM結構替換到舊的DOM(第一次舊的為undefined)，渲染到頁面中。

2.當狀態變化的時候，新渲染一顆虛擬DOM樹和原來舊的虛擬DOM樹對比，對比之后記錄下差異。

3.將最終由差異的部分轉化成真實DOM結構渲染到頁面上。

實現

在舊的虛擬節點和新的虛擬節點的對比過程中會出現以下幾種情況,下面我們以Vue為例看Vue2.0是Diff算法是怎么實現的:

比較兩個元素的標簽

如果標簽不一樣的話直接替換掉,例如:div變成p

div->p 
 
<<<<<<<HEAD 
<p>前端簡報</p> 
 
========= 
 
<div>前端簡報</div> 
>>>>>>>>

判斷虛擬節點的tag屬性是否相等，如果不相等將新的虛擬DOM樹轉化為真實DOM結構把原來節點替換掉

if (oldVnode.tag != vnode.tag) { 
  return oldVnode.el.parentNode.replaceChild(createElm(vnode), oldVnode.el); 
}

效果圖:

比較兩個元素的文本

當標簽一樣的時候比較文本是否一樣。如果文本不一樣的話那么直接替換掉文本內容。

<<<<<<<HEAD 
<div>前端</div> 
========= 
<div>簡報</div> 
>>>>>>>>

兩個節點的tag都是div，故比較孩子虛擬DOM樹的是否一樣,孩子的tag為undefined說明是文本節點，此時比較本文內容text是否一致即可

if (!oldVnode.tag) { 
    //文本的對比 
    if (oldVnode.text != vnode.text) { 
      return (oldVnode.el.textContent = vnode.text); 
    } 
  }

效果圖：

比較標簽屬性

如果兩個標簽一樣那么比較標簽的屬性，當屬性更新的時候通過新舊屬性的對比會出現下面幾種情況：

1、屬性對比

如果舊的虛擬節點有，新的虛擬節點沒有那么需要刪除舊的虛擬節點上的屬性。

let newProps = vnode.data || {}; //新的屬性 
let el = vnode.el; 
//老的有 新的沒有 需要刪除屬性 
for (let key in oldProps) { 
  if (!newProps[key]) { 
    el.removeAttribute(key); //移除真實dom的屬性 
  } 
}

反過來，如果舊的虛擬節點沒有，新的虛擬節點有那么直接設置新的屬性即可

//新的有 那就直接用新的去更新即可 
for (let key in newProps) { 
    el.setAttribute(key, newProps[key]); 
}

對應的源碼地址:src\platforms\web\runtime\modules\attrs.js

2、樣式處理

如果老的樣式中存在新的樣式沒有那么刪除老的樣式。

- style={color:red} 
+ style={background:red}

let newStyle = newProps.style || {}; 
let oldStyle = oldProps.style || {}; 
//老的樣式中有的 新的沒有  刪除老的樣式 
for (let key in oldStyle) { 
  if (!newStyle[key]) { 
    el.style[key] = ""; 
  } 
}

相反如果老的樣式沒有，新的樣式存在那么直接更新新的樣式即可

for (let key in newProps) { 
  if (key == "style") { 
    for (let styleName in newProps.style) { 
      el.style[styleName] = newProps.style[styleName]; 
    } 
  }  
}

對應的源碼地址:src\platforms\web\runtime\modules\style.js

3、類名處理

對于類名處理我們使用新節點的類名

- class="title ant-title" 
+ class="title ant-mian-title"

for (let key in newProps) { 
 if (key == "class") { 
    el.className = newProps.class; 
}

對應的源碼地址src\platforms\web\runtime\modules\class.js

比較兒子

在比較兒子的過程中可以分為以下幾種情況:

1、老節點有兒子，新節點沒有兒子刪除老節點的兒子即可

if (isDef(oldCh)) { 
  removeVnodes(oldCh, 0, oldCh.length - 1) 
}  
========================================= 
if (oldChildren.length > 0) { 
     el.innerHTML = ""; 
}

2、老節點沒有兒子，新節點有兒子遍歷children轉化為真實的DOM結構添加到頁面中

if (isDef(ch)) { 
  if (isDef(oldVnode.text)) nodeOps.setTextContent(elm, '') 
  addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue) 
}  
=============================================================== 
if (newChildren.length > 0) { 
  for (let i = 0; i < newChildren.length; i++) { 
     let child = newChildren[i]; 
     el.appendChild(createElm(child)); 
  } 
}

3、老節點有兒子，新節點有兒子

當老節點的兒子和新節點的兒子都存在并且不相等的時候，這種情況比較復雜也是diff算法的核心。

在vue2.0中比較老節點和新節點區別的時候采用了雙指針的方式，通過同時向同一個方向循環老節點和新節點，只要有一個節點循環完成就結束循環。如果是老節點先結束，那么將新節點剩余的元素添加到渲染列表;如果是新節點先結束，那么將舊節點剩余的元素刪除即可。

定義開頭指針其中包括老節點的開始位置和結束位置，新節點的開始位置和結束位置。

let oldStartIndex = 0; //老的索引 
 let oldStartVnode = oldChildren[0]; //老的索引指向的節點 
 let oldEndIndex = oldChildren.length - 1; 
 let oldEndVnode = oldChildren[oldEndIndex]; 
 
 let newStartIndex = 0; //新的索引 
 let newStartVnode = newChildren[0]; //新的索引指向的節點 
 let newEndIndex = newChildren.length - 1; 
 let newEndVnode = newChildren[newEndIndex];

通過判斷兩個節點的key和tag是否相等來確定同一元素

function sameVnode (a, b) { 
  return ( 
    a.key === b.key && ( 
      ( 
        a.tag === b.tag && 
        ... 
      ) || ( 
        ... 
      ) 
    ) 
  ) 
}

正序排列

如果多余的節點的右邊的話，那么從左往右依次判斷老的開始節點和新的開始節點是否是同一節點,如果是同一節點調用patchVode方法去遞歸子節點，將老節點和新節點的下標加1向右移動，直到下標大于children的長度。

if (sameVnode(oldStartVnode, newStartVnode)) { 
  patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) 
  oldStartVnode = oldCh[++oldStartIdx] 
  newStartVnode = newCh[++newStartIdx] 
}

效果圖:

如果是新節點多余添加到渲染視圖，如上圖從左到右對比時，g節點的下一個el是null，insertBefore相當于appendChild方法向后插入;如果是從右向左，g節點的下一個el是a，那么采用insertBefore相當于向a前面插入節點。

if (oldStartIndex > oldEndIndex) { 
     for (let i = newStartIndex; i <= newEndIndex; i++) { 
      let ele = 
        newChildren[newEndIndex + 1] == null 
          ? null 
          : newChildren[newEndIndex + 1].el; 
      parent.insertBefore(createElm(newChildren[i]), ele); 
    } 
}

如果是老節點多余，那么說明這些節點是不需要的，刪除掉即可，如果在刪除的過程中出現null，說明這個節點已經處理過了跳過即可。

if(newStartIdx > newEndIdx){ 
  for (let i = oldStartIndex; i <= oldEndIndex; i++) { 
     let child = oldChildren[i]; 
     if(child!= undefined){ 
       parent.removeChild(child.el); 
     } 
  } 
}

如果多余的節點在左邊，從新老節點的結束節點開始下標依次減1

if (sameVnode(oldEndVnode, newEndVnode)) { 
  patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx) 
  oldEndVnode = oldCh[--oldEndIdx] 
  newEndVnode = newCh[--newEndIdx] 
}

反轉排列

如果遇到新老節點反轉的情況，通過老節點的開始節點和新節點的結束節點作對比或者老節點和結束節點和新節點的開始節點作對比。

如果老節點的開始節點和新節點的結束節點是同一節點，那么將老的開始節點插入到老的結束節點的下一個節點之前，然后依次分別向右向左移動節點對應的下標，獲取對應的值繼續遍歷。

if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right 
  patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue, newCh, newEndIdx) 
  canMove && nodeOps.insertBefore(parentElm, oldStartVnode.elm, nodeOps.nextSibling(oldEndVnode.elm)) 
  oldStartVnode = oldCh[++oldStartIdx] 
  newEndVnode = newCh[--newEndIdx] 
}

如果老節點的結束節點和新節點的開始節點是同一節點嗎,那么將老節點的結束節點插入到老節點的開始節點前面，然后依次分別向左向右移動節點對應的下標，獲取對應的值繼續遍歷。

if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left 
  patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue, newCh, newStartIdx) 
  canMove && nodeOps.insertBefore(parentElm, oldEndVnode.elm, oldStartVnode.elm) 
  oldEndVnode = oldCh[--oldEndIdx] 
  newStartVnode = newCh[++newStartIdx] 
}

毫無關系排列

如果在對比的過程中兒子之間沒有任何的關系，通過從新節點的開始節點開始依次和老節點的所有節點作對比，如果沒有相同的就創建新的節點插入的老節點的開始節點之前，如果在循環的過程中找到了相同的元素，那么直接復用老元素，將和新節點相同的老節點插入到老節點的開始節點之前，為了防止數組的塌陷問題，將移走的老節點的位置設為undefined，最后將多余的老節點全部刪除即可。

設置緩存組使用老節點的key和下標做一個映射表，新節點的key去老的映射表里篩選，如果沒有篩選到，那么就不復用直接創建新節點插入到老節點的開始節點之前。

function createKeyToOldIdx (children) { 
  let i, key 
  const map = {} 
   children.forEach((item, index) => { 
      if (isDef（item.key）) { 
        map[item.key] = index; //{a:0,b:1,c:2,d:3,e:4,f:5,g:6} 
      } 
  return map 
}

如果在老節點中找到，那么移動老節點到老節點開始節點之前

let map = createKeyToOldIdx(oldChildren); 
 //兒子之間沒有關系 
let moveIndex = map[newStartVnode.key];  //拿到開頭的虛擬節點的key去老的里面找 
 
if(moveIndex == undefined){ 
  parent.insertBefore(createElm(newStartVnode),oldStartVnode.el); 
}else{ 
  let moveVNode = oldChildren[moveIndex];  //這個老的虛擬節點需要移動 
  oldChildren[moveIndex] = null; 
  parent.insertBefore(moveVNode.el,oldStartVnode.el); 
  patch(moveVNode,newStartVnode)  //比較屬性和兒子 
} 
newStartVnode = newChildren[++newStartIndex]  //用新的不停的去老的里面找

在移動的過程中開始指針和結束指針可能存在指向null的情況，如果指向null的話那么無法在進行比較，可以直接跳過，指向下一個元素即可。

if (isUndef(oldStartVnode)) { 
  oldStartVnode = oldCh[++oldStartIdx] // Vnode has been moved left 
} else if (isUndef(oldEndVnode)) { 
  oldEndVnode = oldCh[--oldEndIdx] 
}

源碼地址：src/core/vdom/patch.js

為什么要使用key?

人丑話不多先看圖

有key

沒有key

如上圖所示，第一個圖為有key的情況，第二個圖為沒有key的情況，可以很明顯的看到所展示內容如果有key的話，復用了key為A，B，C，D的4個節點，結果只是將新創建的E節點插入到C節點的前面完成渲染。如果沒有key的話，那么創建了E，C，D三個節點，降低了復用率，性能方面肯定沒有有key 的情況高。

為什么不能用index作為key呢?

平時開發過程中,如果只是通過頁面靜態渲染是可以使用index作為key的，如果在頁面上有復雜的邏輯變化，那么使用index作為key相當于沒有key。

<li index=0>A</li>      <li index=0>C</li> 
<li index=1>B</li>      <li index=1>B</li> 
<li index=2>C</li>      <li index=2>A</li>

如上代碼所示，將下標為0和2的A和C變換位置之后需要重新創建節點A和C,此時C的下標為0，A的下標為2。而以id或者唯一標識作為key的話，相當于是將A和C元素的位置進行平移。平移的性能比創建節點的性能高。

在使用index作為key的時候還會產生意想不到的問題，假如我們把B節點刪除，我們最開始取值為B，現在取值變成了C。

總結

Vue2.0的diff算法pathVode方法的基本思路可以總結為以下幾點：

1.判斷oldVode和newVode是否是同一對象，如果是的話直接return。2.是定義真實DOM為el。

3.如果oldVode和newVode都有文本節點并且不相等，那么將old的文本節點設置為newVode的文本節點。

4.如果oldVode有子節點newVode沒有，那么刪掉子節點。

5.如果oldVode沒有子節點newVode有。那么將子節點轉化為真實DOM添加到el中。6.如果都有子節點，那么執行updateChildren函數比較子節點

以上就是Diff算法的整個過程，它對整個Vue渲染過程的性能有著至關重要的作用。

責任編輯：姜華來源：前端簡報

算法虛擬DOM 前端