「源碼剖析」如何實(shí)現(xiàn)一個(gè)虛擬DOM算法

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

我們希望是在更新的時(shí)候通過新渲染的虛擬DOM樹和舊的虛擬DOM樹進(jìn)行對(duì)比,記錄這兩顆樹的差異。記錄下來的不同就是我們需要對(duì)頁面真正的DOM操作，然后把它們渲染在真正的DOM結(jié)構(gòu)上，頁面就對(duì)應(yīng)的變化了。

[[378869]]

上篇文章《虛擬DOM如何進(jìn)化為真實(shí)DOM》中講到了如何通過虛擬DOM樹轉(zhuǎn)化為真實(shí)DOM渲染到頁面中。但是在渲染的過程中，我們直接將新的虛擬DOM樹轉(zhuǎn)化成真實(shí)DOM替換掉舊的DOM結(jié)構(gòu)。當(dāng)真實(shí)的DOM中的狀態(tài)或者內(nèi)容發(fā)生變化的時(shí)候，重新渲染新的虛擬DOM樹再替換掉舊的，這樣的話會(huì)顯得很無力。設(shè)想一種情景，當(dāng)我們對(duì)整個(gè)DOM結(jié)構(gòu)中只是修改了一個(gè)小的數(shù)據(jù)甚至是一個(gè)標(biāo)點(diǎn)符號(hào)的時(shí)候或者數(shù)據(jù)量很大的時(shí)候，我們要把原來舊的DOM結(jié)構(gòu)全部替換掉，這樣的話對(duì)計(jì)算機(jī)而言太浪費(fèi)性能了。

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

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

1.將虛擬DOM結(jié)構(gòu)轉(zhuǎn)化為真實(shí)的DOM結(jié)構(gòu)替換到舊的DOM(第一次舊的為undefined)，渲染到頁面中。

2.當(dāng)狀態(tài)變化的時(shí)候，新渲染一顆虛擬DOM樹和原來舊的虛擬DOM樹對(duì)比，對(duì)比之后記錄下差異。

3.將最終由差異的部分轉(zhuǎn)化成真實(shí)DOM結(jié)構(gòu)渲染到頁面上。

實(shí)現(xiàn)

在舊的虛擬節(jié)點(diǎn)和新的虛擬節(jié)點(diǎn)的對(duì)比過程中會(huì)出現(xiàn)以下幾種情況,下面我們以Vue為例看Vue2.0是Diff算法是怎么實(shí)現(xiàn)的:

比較兩個(gè)元素的標(biāo)簽

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

div->p 
 
<<<<<<<HEAD 
<p>前端簡(jiǎn)報(bào)</p> 
 
========= 
 
<div>前端簡(jiǎn)報(bào)</div> 
>>>>>>>>

判斷虛擬節(jié)點(diǎn)的tag屬性是否相等，如果不相等將新的虛擬DOM樹轉(zhuǎn)化為真實(shí)DOM結(jié)構(gòu)把原來節(jié)點(diǎn)替換掉

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

效果圖:

比較兩個(gè)元素的文本

當(dāng)標(biāo)簽一樣的時(shí)候比較文本是否一樣。如果文本不一樣的話那么直接替換掉文本內(nèi)容。

<<<<<<<HEAD 
<div>前端</div> 
========= 
<div>簡(jiǎn)報(bào)</div> 
>>>>>>>>

兩個(gè)節(jié)點(diǎn)的tag都是div，故比較孩子虛擬DOM樹的是否一樣,孩子的tag為undefined說明是文本節(jié)點(diǎn)，此時(shí)比較本文內(nèi)容text是否一致即可

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

效果圖：

比較標(biāo)簽屬性

如果兩個(gè)標(biāo)簽一樣那么比較標(biāo)簽的屬性，當(dāng)屬性更新的時(shí)候通過新舊屬性的對(duì)比會(huì)出現(xiàn)下面幾種情況：

1、屬性對(duì)比

如果舊的虛擬節(jié)點(diǎn)有，新的虛擬節(jié)點(diǎn)沒有那么需要?jiǎng)h除舊的虛擬節(jié)點(diǎn)上的屬性。

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

反過來，如果舊的虛擬節(jié)點(diǎn)沒有，新的虛擬節(jié)點(diǎn)有那么直接設(shè)置新的屬性即可

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

對(duì)應(yīng)的源碼地址:src\platforms\web\runtime\modules\attrs.js

2、樣式處理

如果老的樣式中存在新的樣式?jīng)]有那么刪除老的樣式。

- 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] = ""; 
  } 
}

相反如果老的樣式?jīng)]有，新的樣式存在那么直接更新新的樣式即可

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

對(duì)應(yīng)的源碼地址:src\platforms\web\runtime\modules\style.js

3、類名處理

對(duì)于類名處理我們使用新節(jié)點(diǎn)的類名

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

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

對(duì)應(yīng)的源碼地址src\platforms\web\runtime\modules\class.js

比較兒子

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

1、老節(jié)點(diǎn)有兒子，新節(jié)點(diǎn)沒有兒子刪除老節(jié)點(diǎn)的兒子即可

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

2、老節(jié)點(diǎn)沒有兒子，新節(jié)點(diǎn)有兒子遍歷children轉(zhuǎn)化為真實(shí)的DOM結(jié)構(gòu)添加到頁面中

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、老節(jié)點(diǎn)有兒子，新節(jié)點(diǎn)有兒子

當(dāng)老節(jié)點(diǎn)的兒子和新節(jié)點(diǎn)的兒子都存在并且不相等的時(shí)候，這種情況比較復(fù)雜也是diff算法的核心。

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

定義開頭指針其中包括老節(jié)點(diǎn)的開始位置和結(jié)束位置，新節(jié)點(diǎn)的開始位置和結(jié)束位置。

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

通過判斷兩個(gè)節(jié)點(diǎn)的key和tag是否相等來確定同一元素

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

正序排列

如果多余的節(jié)點(diǎn)的右邊的話，那么從左往右依次判斷老的開始節(jié)點(diǎn)和新的開始節(jié)點(diǎn)是否是同一節(jié)點(diǎn),如果是同一節(jié)點(diǎn)調(diào)用patchVode方法去遞歸子節(jié)點(diǎn)，將老節(jié)點(diǎn)和新節(jié)點(diǎn)的下標(biāo)加1向右移動(dòng)，直到下標(biāo)大于children的長(zhǎng)度。

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

效果圖:

如果是新節(jié)點(diǎn)多余添加到渲染視圖，如上圖從左到右對(duì)比時(shí)，g節(jié)點(diǎn)的下一個(gè)el是null，insertBefore相當(dāng)于appendChild方法向后插入;如果是從右向左，g節(jié)點(diǎn)的下一個(gè)el是a，那么采用insertBefore相當(dāng)于向a前面插入節(jié)點(diǎn)。

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); 
    } 
}

如果是老節(jié)點(diǎn)多余，那么說明這些節(jié)點(diǎn)是不需要的，刪除掉即可，如果在刪除的過程中出現(xiàn)null，說明這個(gè)節(jié)點(diǎn)已經(jīng)處理過了跳過即可。

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

如果多余的節(jié)點(diǎn)在左邊，從新老節(jié)點(diǎn)的結(jié)束節(jié)點(diǎn)開始下標(biāo)依次減1

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

反轉(zhuǎn)排列

如果遇到新老節(jié)點(diǎn)反轉(zhuǎn)的情況，通過老節(jié)點(diǎn)的開始節(jié)點(diǎn)和新節(jié)點(diǎn)的結(jié)束節(jié)點(diǎn)作對(duì)比或者老節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)和新節(jié)點(diǎn)的開始節(jié)點(diǎn)作對(duì)比。

如果老節(jié)點(diǎn)的開始節(jié)點(diǎn)和新節(jié)點(diǎn)的結(jié)束節(jié)點(diǎn)是同一節(jié)點(diǎn)，那么將老的開始節(jié)點(diǎn)插入到老的結(jié)束節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)之前，然后依次分別向右向左移動(dòng)節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)，獲取對(duì)應(yīng)的值繼續(xù)遍歷。

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] 
}

如果老節(jié)點(diǎn)的結(jié)束節(jié)點(diǎn)和新節(jié)點(diǎn)的開始節(jié)點(diǎn)是同一節(jié)點(diǎn)嗎,那么將老節(jié)點(diǎn)的結(jié)束節(jié)點(diǎn)插入到老節(jié)點(diǎn)的開始節(jié)點(diǎn)前面，然后依次分別向左向右移動(dòng)節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)，獲取對(duì)應(yīng)的值繼續(xù)遍歷。

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] 
}

毫無關(guān)系排列

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

設(shè)置緩存組使用老節(jié)點(diǎn)的key和下標(biāo)做一個(gè)映射表，新節(jié)點(diǎn)的key去老的映射表里篩選，如果沒有篩選到，那么就不復(fù)用直接創(chuàng)建新節(jié)點(diǎn)插入到老節(jié)點(diǎn)的開始節(jié)點(diǎn)之前。

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 
}

如果在老節(jié)點(diǎn)中找到，那么移動(dòng)老節(jié)點(diǎn)到老節(jié)點(diǎn)開始節(jié)點(diǎn)之前

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

在移動(dòng)的過程中開始指針和結(jié)束指針可能存在指向null的情況，如果指向null的話那么無法在進(jìn)行比較，可以直接跳過，指向下一個(gè)元素即可。

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

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

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

平時(shí)開發(fā)過程中,如果只是通過頁面靜態(tài)渲染是可以使用index作為key的，如果在頁面上有復(fù)雜的邏輯變化，那么使用index作為key相當(dāng)于沒有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>

如上代碼所示，將下標(biāo)為0和2的A和C變換位置之后需要重新創(chuàng)建節(jié)點(diǎn)A和C,此時(shí)C的下標(biāo)為0，A的下標(biāo)為2。而以id或者唯一標(biāo)識(shí)作為key的話，相當(dāng)于是將A和C元素的位置進(jìn)行平移。平移的性能比創(chuàng)建節(jié)點(diǎn)的性能高。

在使用index作為key的時(shí)候還會(huì)產(chǎn)生意想不到的問題，假如我們把B節(jié)點(diǎn)刪除，我們最開始取值為B，現(xiàn)在取值變成了C。

總結(jié)

Vue2.0的diff算法pathVode方法的基本思路可以總結(jié)為以下幾點(diǎn)：

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

3.如果oldVode和newVode都有文本節(jié)點(diǎn)并且不相等，那么將old的文本節(jié)點(diǎn)設(shè)置為newVode的文本節(jié)點(diǎn)。

4.如果oldVode有子節(jié)點(diǎn)newVode沒有，那么刪掉子節(jié)點(diǎn)。

5.如果oldVode沒有子節(jié)點(diǎn)newVode有。那么將子節(jié)點(diǎn)轉(zhuǎn)化為真實(shí)DOM添加到el中。6.如果都有子節(jié)點(diǎn)，那么執(zhí)行updateChildren函數(shù)比較子節(jié)點(diǎn)

以上就是Diff算法的整個(gè)過程，它對(duì)整個(gè)Vue渲染過程的性能有著至關(guān)重要的作用。