vue虛擬dom和diff算法

2022 年 6 月 13 日
筆記
diff算法, VUE

vue的虛擬dom和diff算法

1.虛擬dom

虛擬dom，我的理解就是通過js對象的方式來具體化每一個節點，把dom樹上面的每個節點都變為對象里的一個元素，元素的子元素變為子節點，節點上面的class、id、attribute等屬性變為data內的值，然後通過dom上面的createElement、appendChild、insertBefore等方法進行生成dom樹。

let VNode = {
    sel:'div',
    data:{
        key:0,
        props:{},
        attrs:{},
        class:{},
        style:{},
        fn:{}
    },
    text:'虛擬dom',
    elm:'<div>虛擬dom</div>'
    children:[
        {
            sel:'div',
            data:{
                key:0,
                props:{},
                attrs:{},
                class:{},
                style:{},
                fn:{}
            },
            text:'虛擬dom children',
            elm:'<div>虛擬dom children</div>'
            children:[]
        }
    ]
}

2.diff算法

看了diff算法後感覺寫的真是巧妙，真正做到了最小量更新。

diff是當父節點相同時用來對子節點進行最小量更新的算法。

diff算法採用四個指針：舊節點開始指針，舊節點結束指針，新節點開始指針，新節點結束指針；

（上方虛擬節點中的key就是為了在進行diff算法時判斷是否是同一個節點便於最小量更新）

while(舊節點開始指針<=舊節點結束指針&&新節點開始指針<=新節點結束指針){

分為以下五種情況：（前四種情況）

「

當進行下面5種判斷後可能會出現新節點[新節點開始指針] 舊節點[舊節點開始指針] 新節點[新節點結束指針] 舊節點[舊節點結束指針]為空值的情況，如果出現空值則代表當前節點已經處理過了，所以就需要將指針++或者—

if(舊節點[舊節點開始指針] ==null){

舊節點開始指針++

}else if(舊節點[舊節點結束指針]==null){

舊節點結束指針–

}else if(新節點[新節點開始指針] ==null){

新節點開始指針++

}else if(新節點[新節點結束指針] ==null){

新節點結束指針–

}

」

1、新節點[新節點開始指針] 對比 舊節點[舊節點開始指針]

如果符合此種情況，則代表新節點[新節點開始指針] 與 舊節點[舊節點開始指針] 為同一個節點，實行最小量更新，即只更新節點內的屬性而不進行dom銷毀創建操作，完成更新後 新節點開始指針++，舊節點開始指針++

2、新節點[新節點結束指針] 對比 舊節點[舊節點結束指針]

如果符合此種情況，則代表新節點[新節點結束指針] 與 舊節點[舊節點結束指針] 為同一個節點，實行最小量更新，即只更新節點內的屬性而不進行dom銷毀創建操作，完成更新後 新節點結束指針–，舊節點結束指針–

3、新節點[新節點結束指針] 對比 舊節點[舊節點開始指針]

如果符合此種情況，則代表新節點[新節點結束指針] 與 舊節點[舊節點開始指針] 為同一個節點，實行最小量更新，先更新節點內的屬性，然後使用insertBefore將舊節點[舊節點開始指針] 移動到舊節點[舊節點結束指針] 之後，（注意：此處要移動到舊節點[舊節點結束節點] 後，而不是所有舊節點後，因為這裡的舊節點結束指針是會變化的）,

    父節點.insertBefore(舊節點[舊節點開始指針].elm, 舊節點[舊節點結束指針].elm.nextSibling)

完成操作後 新節點結束指針–，舊節點開始指針++

4、新節點[新節點開始指針] 對比 舊節點[舊節點結束指針] 如果符合此種情況，則代表新節點[新節點開始指針] 與 舊節點[舊節點結束指針] 為同一個節點，實行最小量更新，先更新節點內的屬性，然後使用insertBefore將舊節點[舊節點結束指針] 移動到舊節點[舊節點開始指針] 前，（注意：此處要移動到舊節點[舊節點開始指針] 前，而不是所有舊節點前，因為舊節點開始指針也是會發生變化的）

    父節點.insertBefore(舊節點[舊節點結束指針].elm, 舊節點[舊節點開始指針].elm)

完成操作後，舊節點結束指針–，新節點開始指針++

5、遍歷舊節點數組，生成一個以key為鍵，index為值的對象為舊節點keyIndexMap，然後查詢新節點[新節點開始指針]中的key是否在舊節點keyIndexMap中存在；

如果不存在，則證明新節點[新節點開始指針]在舊節點列表中不存在，此時需要創建新節點[新節點開始指針]為真實dom，並將其插入至舊節點[舊節點開始指針]前(因為此時新節點[新節點開始指針]一定處於全部未處理的舊節點前)

父節點.insertBefore(創建dom(新節點[新節點開始指針]), 舊節點[舊節點開始指針].elm)

如果存在則先需要判斷舊節點[舊節點keyIndexMap[新節點[新節點開始指針][key]]]與新節點[新節點開始指針]的sel(標籤)是否相同：

如果相同則代表為同一個標籤，則進行最小量更新，先更新節點內的屬性，然後insertBefore將舊節點[舊節點keyIndexMap[新節點[新節點開始指針][key]]]移動到舊節點[舊節點開始指針] 前，然後將舊節點[舊節點keyIndexMap[新節點[新節點開始指針][key]]]設置為undefined，代表當前節點處理過了；

如果不同則代表不是同一個標籤，則只創建新節點[新節點開始指針]的真實dom，然後將其插入到舊節點[舊節點開始節點]。

最後新節點開始指針++

}

當以上循環完成後可能還會出現沒有處理到的節點，所以還需要再查找沒有處理到的節點：

如果是新節點開始指針<=新節點結束指針，則代表新節點列表內還有沒有處理的節點，沒有處理的節點全部為新增節點，此時需要遍歷新節點[新節點開始指針]（包含）至新節點[新節點結束指針]（包含）之間的節點，然後將其添加至新節點[新節點結束指針+1]之前（新節點[新節點結束指針+1]可能為空，新節點[新節點結束指針+1]為空時可添加到最後）

        for (let i = 新節點開始節點; i <= 新節點結束節點; i++) {
          //insertBefore可以自動識別空值，如果是空值，則插入到最後
          父節點.insertBefore(創建dom(新節點[i]), 新節點[新節點結束節點-1]?.elm)
        }

如果是舊節點開始指針<=舊節點結束指針，則代表舊節點內還有沒有處理的節點，沒有處理的節點全部為需要刪除節點，此時需要遍歷舊節點[舊節點開始指針]（包含）至舊節點[舊節點結束指針]（包含）之間的節點，然後將其全部刪除。

        for (let i = 舊節點開始指針; i <= 舊節點結束指針; i++) {
          舊節點[i] && (父節點.removeChild(舊節點[i].elm))
        }

以上就是我對diff算法的理解，下面貼上代碼(閹割版，部分情況沒有考慮，旨在學習diff算法，可能會有bug)：

//updateChildren文件
import { sameVnode } from './is'
import patchVnode from './patchVnode'
import createElement from './createElement'

export default functionupdateChildren  (parentElm, oldCh, newCh) {
  console.log('updateChildren')
  console.log(parentElm, oldCh, newCh)

  //舊前
  let oldStartIdx = 0
  //新前
  let newStartIdx = 0
  //舊後
  let oldEndIdx = oldCh.length - 1
  //新後
  let newEndIdx = newCh.length - 1
  //舊節點
  let oldStartVnode = oldCh[0]
  //舊後節點
  let oldEndVnode = oldCh[oldEndIdx]
  //新節點
  let newStartVnode = newCh[0]
  //新後節點
  let newEndVnode = newCh[newEndIdx]

  let keyMap = {}
//  開始循環
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // debugger
    console.log('while')
    if (oldStartVnode === undefined || oldCh[oldStartIdx] === undefined) {
      oldStartVnode = oldCh[++oldStartIdx]
    } else if (oldEndVnode === undefined || oldCh[oldEndIdx] === undefined) {
      oldEndVnode = oldCh[--oldEndIdx]
    } else if (newStartVnode === undefined || newCh[newStartIdx] === undefined) {
      newStartVnode = newCh[++newStartIdx]
    } else if (newEndVnode === undefined || newCh[newEndIdx] === undefined) {
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      //新前和舊前是同一個節點
      console.log('新前和舊前是同一個節點')
      patchVnode(oldStartVnode, newStartVnode)
      oldStartVnode = oldCh[++oldStartIdx]
      newStartVnode = newCh[++newStartIdx]
    } else if (sameVnode(oldEndVnode, newEndVnode)) {//舊後和新後是同一個節點
      console.log('舊後和新後是同一個節點')
      patchVnode(oldEndVnode, newEndVnode)
      oldEndVnode = oldCh[--oldEndIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldStartVnode, newEndVnode)) {//新後和舊前是同一個節點
      console.log('新後和舊前是同一個節點')
      patchVnode(oldStartVnode, newEndVnode)
      //當新後節點是舊前節點時，此時需要移動節點，移動舊前節點到舊後的後面
      parentElm.insertBefore(oldStartVnode.elm, oldEndVnode.elm.nextSibling)
      oldStartVnode = oldCh[++oldStartIdx]
      newEndVnode = newCh[--newEndIdx]
    } else if (sameVnode(oldEndVnode, newStartVnode)) {//舊後和新前是同一個節點
      console.log('舊後和新前是同一個節點')
      //  當舊後和新前是同一個節點時，此時需要移動舊後節點到舊前節點的前面
      patchVnode(oldEndVnode, newStartVnode)
      parentElm.insertBefore(oldEndVnode.elm, oldStartVnode.elm)
      oldEndVnode = oldCh[--oldEndIdx]
      newStartVnode = newCh[++newStartIdx]
    } else {
      //前四種都沒有命中
      if (Object.keys(keyMap).length === 0) {
        keyMap = {}
        for (let i = oldStartIdx; i <= oldEndIdx; i++) {
          const key = oldCh[i].key
          if (key) {
            keyMap[key] = i
          }
        }
      }
      console.log(keyMap)
      //尋找當前節點在keyMap中的位置
      const idxInOld = keyMap[newStartVnode.key]
      console.log(idxInOld)
      if (!idxInOld) {
        //新節點不在舊節點中
        parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
      } else {
        //  新節點在舊節點中,需要移動
        const elmToMove = oldCh[idxInOld]
        if (elmToMove.sel !== newStartVnode.sel) {
          parentElm.insertBefore(createElement(newStartVnode), oldStartVnode.elm)
        } else {
          patchVnode(elmToMove, newStartVnode)
          //  把這項設置為undefined，表示已經移動過了
          oldCh[idxInOld] = undefined
          parentElm.insertBefore(elmToMove.elm, oldStartVnode.elm)
        }
      }
      //指針向後移動
      newStartVnode = newCh[++newStartIdx]
    }
  }
// 繼續查詢是否有剩餘節點
  if (newStartIdx <= newEndIdx) {
    console.log('新節點還有剩餘節點沒有處理', newStartIdx, newEndIdx)
    const before = newCh[newEndIdx + 1]?.elm
    console.log(before)
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      //insertBefore可以自動識別undefined，如果是undefined，則插入到最後
      parentElm.insertBefore(createElement(newCh[i]), before)
    }
  } else if (oldStartIdx <= oldEndIdx) {
    console.log('舊節點還有剩餘節點沒有處理', oldStartIdx, oldEndIdx)
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      oldCh[i] && (parentElm.removeChild(oldCh[i].elm))
    }
  }
}

let arr = [1, 1, 2, 35, 9, 2, 9]
arr.reduce((p, n) => {
  return p ^ n
}, 0)

//is文件
export function sameVnode (vnode1, vnode2) {
  return vnode1.sel === vnode2.sel && vnode1.key === vnode2.key;
}

//createElement文件
//真正創建dom
export default function createElement (vnode) {
  let domNode = document.createElement(vnode.sel);
  if (
    vnode.text !== "" &&
    (vnode.children === undefined || vnode.children.length === 0)
  ) {
    domNode.innerText = vnode.text;
    //  補充elm

  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    for (let i = 0; i < vnode.children.length; i++) {
      domNode.appendChild(createElement(vnode.children[i]));
    }
  }
  vnode.elm = domNode;
  return vnode.elm
}

//patchVnode文件
import createElement from './createElement'
import updateChildren from './updateChildren'

export default function patchVnode (oldVnode, newVnode) {
  // console.log('patchVnode')
  if (oldVnode === newVnode) return
  if (newVnode.text && (!newVnode.children || newVnode.children.length === 0)) {//判斷newVnode的text是否為空，且不等於oldVnode的text，如果滿足以上條件，則更新text
    oldVnode.text !== newVnode.text && (oldVnode.elm.innerText = newVnode.text);
  } else {//newVnode的text為空，則判斷newVnode的children是否為空，如果不為空，則更新children
    //  新節點沒有text屬性
    if (oldVnode.children && oldVnode.children.length > 0) {
      //  老節點有children，新節點也有children
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
    } else {
      //  老的沒有children，新的有children
      oldVnode.elm.innerHTML = '';
      for (let i = 0; i < newVnode.children.length; i++) {
        let dom = createElement(newVnode.children[i])
        oldVnode.elm.appendChild(dom)
      }
    }
  }
}

//patch文件
import vnode from "./vnode";
import createElement from "./createElement";
import patchVnode from './patchVnode'
import { sameVnode } from './is'

export default function (oldVnode, newVnode) {
  // console.log(oldVnode, newVnode)
  //判斷傳入的第一個參數，是dom節點還是vnode
  if (oldVnode.sel === "" || oldVnode.sel === undefined) {
    //傳入的如果是dom節點需要包裝為虛擬節點
    oldVnode = vnode(
      oldVnode.tagName.toLowerCase(),
      {},
      [],
      undefined,
      oldVnode,
    );
  }
  //  判斷oldVnode和newVnode是否是同一個節點
  if (sameVnode(oldVnode, newVnode)) {
    // console.log("是同一個節點");
    patchVnode(oldVnode, newVnode);
  } else {
    // console.log("不是同一個節點");
    let newVnodeElm = createElement(newVnode, oldVnode.elm);
    if (oldVnode.elm.parentNode && newVnodeElm) {
      oldVnode.elm.parentNode.insertBefore(newVnodeElm, oldVnode.elm);
    }
    oldVnode.elm.parentNode.removeChild(oldVnode.elm);
  }
}

//VNode文件
export default function (sel, data, children, text, elm) {
  const key = data.key
  return {
    sel,
    data,
    children,
    text,
    elm,
    key,
  }
}

//h文件

import vnode from './vnode.js'

//h('div',{},'文字')
//h('div',{},'[]')
//h('div',{},h())
export default function (sel, data, c) {
//檢查參數個數
  if (arguments.length !== 3) {
    throw new Error('h()參數個數不正確')

  }
//    檢查C類型
  if (typeof c === 'string' || typeof c === 'number') {
    return vnode(sel, data, undefined, c, undefined)
  } else if (Array.isArray(c)) {
    let children = []
    for (let i = 0; i < c.length; i++) {
      if (!(typeof c[i] === 'object' && c[i].hasOwnProperty('sel'))) {
        throw new Error('傳入的數組參數中有項不是h函數')
      }
      children.push(c[i])
    }
    //  循環結束，children收集完畢
    return vnode(sel, data, children, undefined, undefined)
  } else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
    let children = [c]
    return vnode(sel, data, children, undefined, undefined)
  } else {
    throw new Error('h()參數類型不正確')
  }
}

Tags: diff算法 VUE