我讓虛拟DOM的diff算法過程動起來了

去年寫了一篇文章手寫一個虛拟DOM庫，徹底讓你了解diff算法介紹虛拟DOM的patch過程和diff算法過程，當時使用的是雙端diff算法，今年看到了Vue3使用的已經是快速diff算法，是以也想寫一篇來記錄一下，但是肯定已經有人寫過了，是以就在想能不能有點不一樣的，上次的文章主要是通過畫圖來一步步展示diff算法的每一種情況和過程，是以就在想能不能改成動畫的形式，于是就有了這篇文章。當然目前的實作還是基于雙端diff算法的，後續會補充上快速diff算法。

傳送門：雙端Diff算法動畫示範。

界面就是這樣的，左側可以輸入要比較的新舊VNode清單，然後點選啟動按鈕就會以動畫的形式來展示從頭到尾的過程，右側是水準的三個清單，分别代表的是新舊的VNode清單，以及目前的真實DOM清單，DOM清單初始和舊的VNode清單一緻，算法結束後會和新的VNode清單一緻。

需要說明的是這個動畫隻包含diff算法的過程，不包含patch過程。

先來回顧一下雙端diff算法的函數：

const diff = (el, oldChildren, newChildren) => {
  // 指針
  let oldStartIdx = 0
  let oldEndIdx = oldChildren.length - 1
  let newStartIdx = 0
  let newEndIdx = newChildren.length - 1
  // 節點
  let oldStartVNode = oldChildren[oldStartIdx]
  let oldEndVNode = oldChildren[oldEndIdx]
  let newStartVNode = newChildren[newStartIdx]
  let newEndVNode = newChildren[newEndIdx]
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if (oldStartVNode === null) {
      oldStartVNode = oldChildren[++oldStartIdx]
    } else if (oldEndVNode === null) {
      oldEndVNode = oldChildren[--oldEndIdx]
    } else if (newStartVNode === null) {
      newStartVNode = oldChildren[++newStartIdx]
    } else if (newEndVNode === null) {
      newEndVNode = oldChildren[--newEndIdx]
    } else if (isSameNode(oldStartVNode, newStartVNode)) { // 頭-頭
      patchVNode(oldStartVNode, newStartVNode)
      // 更新指針
      oldStartVNode = oldChildren[++oldStartIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (isSameNode(oldStartVNode, newEndVNode)) { // 頭-尾
      patchVNode(oldStartVNode, newEndVNode)
      // 把oldStartVNode節點移動到最後
      el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)
      // 更新指針
      oldStartVNode = oldChildren[++oldStartIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (isSameNode(oldEndVNode, newStartVNode)) { // 尾-頭
      patchVNode(oldEndVNode, newStartVNode)
      // 把oldEndVNode節點移動到oldStartVNode前
      el.insertBefore(oldEndVNode.el, oldStartVNode.el)
      // 更新指針
      oldEndVNode = oldChildren[--oldEndIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (isSameNode(oldEndVNode, newEndVNode)) { // 尾-尾
      patchVNode(oldEndVNode, newEndVNode)
      // 更新指針
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else {
      let findIndex = findSameNode(oldChildren, newStartVNode)
      // newStartVNode在舊清單裡不存在，那麼是新節點，建立插入
      if (findIndex === -1) {
        el.insertBefore(createEl(newStartVNode), oldStartVNode.el)
      } else { // 在舊清單裡存在，那麼進行patch，并且移動到oldStartVNode前
        let oldVNode = oldChildren[findIndex]
        patchVNode(oldVNode, newStartVNode)
        el.insertBefore(oldVNode.el, oldStartVNode.el)
        // 将該VNode置為空
        oldChildren[findIndex] = null
      }
      newStartVNode = newChildren[++newStartIdx]
    }
  }
  // 舊清單裡存在新清單裡沒有的節點，需要删除
  if (oldStartIdx <= oldEndIdx) {
    for (let i = oldStartIdx; i <= oldEndIdx; i++) {
      removeEvent(oldChildren[i])
      oldChildren[i] && el.removeChild(oldChildren[i].el)
    }
  } else if (newStartIdx <= newEndIdx) {
    let before = newChildren[newEndIdx + 1] ? newChildren[newEndIdx + 1].el : null
    for (let i = newStartIdx; i <= newEndIdx; i++) {
      el.insertBefore(createEl(newChildren[i]), before)
    }
  }
}

該函數具體的實作步驟可以參考之前的文章，本文就不再贅述。

我們想讓這個diff過程動起來，首先要找到動畫的對象都有哪些，從函數的參數開始看，首先oldChildren和 newChildren兩個VNode清單是必不可少的，可以通過兩個水準的清單表示，然後是四個指針，這是雙端diff算法的關鍵，我們通過四個箭頭來表示，指向目前所比較的節點，然後就開啟循環了，循環中新舊VNode清單其實基本上是沒啥變化的，我們實際操作的是VNode對應的真實DOM元素，包括patch打更新檔、移動、删除、新增等等操作，是以我們再來個水準的清單表示目前的真實DOM清單，最開始肯定是和舊的VNode清單是對應的，通過diff算法一步步會變成和新的VNode清單對應。

再來回顧一下建立VNode對象的h函數：

export const h = (tag, data = {}, children) => {
  let text = ''
  let el
  let key
  // 文本節點
  if (typeof children === 'string' || typeof children === 'number') {
    text = children
    children = undefined
  } else if (!Array.isArray(children)) {
    children = undefined
  }
  if (data && data.key) {
    key = data.key
  }
  return {
    tag, // 元素标簽
    children, // 子元素
    text, // 文本節點的文本
    el, // 真實dom
    key,
    data
  }
}

我們輸入的VNode清單資料會使用h函數來建立成VNode對象，是以可以輸入的最簡單的結構如下：

[
  {
    tag: 'div',
    children: '文本節點的内容',
    data: {
      key: 'a'
    }
  }
]

輸入的新舊VNode清單資料會儲存在store中，可以通過如下方式擷取到：

// 輸入的舊VNode清單
store.oldVNode
// 輸入的新VNode清單
store.newVNode

接下來定義相關的變量：

// 指針清單
const oldPointerList = ref([])
const newPointerList = ref([])
// 真實DOM節點清單
const actNodeList = ref([])
// 新舊節點清單
const oldVNodeList = ref([])
const newVNodeList = ref([])
// 提示資訊
const info = ref('')

指針的移動動畫可以使用css的transition屬性來實作，隻要修改指針元素的left值即可，真實DOM清單的移動動畫可以使用Vue的清單過渡元件TransitionGroup來輕松實作，模闆如下：

<div class="playground">
  <!-- 指針 -->
  <div class="pointer">
    <div
         class="pointerItem"
         v-for="item in oldPointerList"
         :key="item.name"
         :style="{ left: item.value * 120 + 'px' }"
         >
      <div class="pointerItemName">{{ item.name }}</div>
      <div class="pointerItemValue">{{ item.value }}</div>
      <img src="../assets/箭頭_向下.svg" alt="" />
    </div>
  </div>
  <div class="nodeListBox">
    <!-- 舊節點清單 -->
    <div class="nodeList">
      <div class="name" v-if="oldVNodeList.length > 0">舊的VNode清單</div>
      <div class="nodes">
        <TransitionGroup name="list">
          <div
               class="nodeWrap"
               v-for="(item, index) in oldVNodeList"
               :key="item ? item.data.key : index"
               >
            <div class="node">{{ item ? item.children : '空' }}</div>
          </div>
        </TransitionGroup>
      </div>
    </div>
    <!-- 新節點清單 -->
    <div class="nodeList">
      <div class="name" v-if="newVNodeList.length > 0">新的VNode清單</div>
      <div class="nodes">
        <TransitionGroup name="list">
          <div
               class="nodeWrap"
               v-for="(item, index) in newVNodeList"
               :key="item.data.key"
               >
            <div class="node">{{ item.children }}</div>
          </div>
        </TransitionGroup>
      </div>
    </div>
    <!-- 提示資訊 -->
    <div class="info">{{ info }}</div>
  </div>
  <!-- 指針 -->
  <div class="pointer">
    <div
         class="pointerItem"
         v-for="item in newPointerList"
         :key="item.name"
         :style="{ left: item.value * 120 + 'px' }"
         >
      <img src="../assets/箭頭_向上.svg" alt="" />
      <div class="pointerItemValue">{{ item.value }}</div>
      <div class="pointerItemName">{{ item.name }}</div>
    </div>
  </div>
  <!-- 真實DOM清單 -->
  <div class="nodeList act" v-if="actNodeList.length > 0">
    <div class="name">真實DOM清單</div>
    <div class="nodes">
      <TransitionGroup name="list">
        <div
             class="nodeWrap"
             v-for="item in actNodeList"
             :key="item.data.key"
             >
          <div class="node">{{ item.children }}</div>
        </div>
      </TransitionGroup>
    </div>
  </div>
</div>

雙端diff算法過程中是不會修改新的VNode清單的，但是舊的VNode清單是有可能被修改的，也就是當首尾比較沒有找到可以複用的節點，但是通過直接在舊的VNode清單中搜尋找到了，那麼會移動該VNode對應的真實DOM，移動後該VNode其實就相當于已經被處理過了，但是該VNode的位置又是在目前指針的中間，不能直接被删除，是以隻好置為空null，是以可以看到模闆中有處理這種情況。

另外我們還建立了一個info元素用來展示提示的文字資訊，作為動畫的描述。

但是這樣還是不夠的，因為每個舊的VNode是有對應的真實DOM元素的，但是我們輸入的隻是一個普通的json資料，是以模闆還需要新增一個清單，作為舊的VNode清單的關聯節點，這個清單隻要提供節點引用即可，不需要可見，是以把它的display設為none：

// 根據輸入的舊VNode清單建立元素
const _oldVNodeList = computed(() => {
  return JSON.parse(store.oldVNode)
})
// 引用DOM元素
const oldNode = ref(null)
const oldNodeList = ref([])

<!-- 隐藏 -->
<div class="hide">
  <div class="nodes" ref="oldNode">
    <div
         v-for="(item, index) in _oldVNodeList"
         :key="index"
         ref="oldNodeList"
         >
      {{ item.children }}
    </div>
  </div>
</div>

然後當我們點選啟動按鈕，就可以給我們的三個清單變量指派了，并使用h函數建立新舊VNode對象，然後傳遞給打更新檔的patch函數就可以開始進行比較更新實際的DOM元素了：

const start = () => {
  nextTick(() => {
    // 表示目前真實的DOM清單
    actNodeList.value = JSON.parse(store.oldVNode)
    // 表示舊的VNode清單
    oldVNodeList.value = JSON.parse(store.oldVNode)
    // 表示新的VNode清單
    newVNodeList.value = JSON.parse(store.newVNode)
    nextTick(() => {
      let oldVNode = h(
        'div',
        { key: 1 },
        JSON.parse(store.oldVNode).map((item, index) => {
          // 建立VNode對象
          let vnode = h(item.tag, item.data, item.children)
          // 關聯真實的DOM元素
          vnode.el = oldNodeList.value[index]
          return vnode
        })
      )
      // 清單的父節點也需要關聯真實的DOM元素
      oldVNode.el = oldNode.value
      let newVNode = h(
        'div',
        { key: 1 },
        JSON.parse(store.newVNode).map(item => {
          return h(item.tag, item.data, item.children)
        })
      )
      // 調用patch函數進行打更新檔
      patch(oldVNode, newVNode)
    })
  })
}

可以看到我們輸入的新舊VNode清單是作為一個節點的子節點的，這是因為隻有當比較的兩個節點都存在非文本節點的子節點時才需要使用diff算法來高效的更新他們的子節點，當patch函數運作完後你可以打開控制台檢視隐藏的DOM清單，會發現是和新的VNode清單保持一緻的，那麼你可能要問，為什麼不直接用這個清單來作為真實DOM清單呢，還要自己額外建立一個actNodeList清單，其實是可以，但是diff算法過程中是使用insertBefore等方法來移動真實DOM節點的，是以不好加過渡動畫，隻會看到節點瞬間換位置，不符合我們的動畫需求。

到這裡效果如下：

接下來我們先把指針搞出來，我們建立一個處理函數對象，這個對象上會挂載一些方法，用于在diff算法過程中調用，在函數中更新相應的變量。

const handles = {
  // 更新指針
  updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx) {
    oldPointerList.value = [
      {
        name: 'oldStartIdx',
        value: oldStartIdx
      },
      {
        name: 'oldEndIdx',
        value: oldEndIdx
      }
    ]
    newPointerList.value = [
      {
        name: 'newStartIdx',
        value: newStartIdx 
      },
      {
        name: 'newEndIdx',
        value: newEndIdx
      }
    ]
  },
}

然後我們就可以在diff函數中通過handles.updatePointers()更新指針了：

const diff = (el, oldChildren, newChildren) => {
  // 指針
  // ...
  handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)
  // ...
}

這樣指針就出來了：

然後在while循環中會不斷改變這四個指針，是以在循環中也需要更新：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  // ...
  handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)
}

但是這樣顯然是不行的，為啥呢，因為循環也就一瞬間就結束了，而我們希望每次都能停留一段時間，很簡單，我們寫個等待函數：

const wait = t => {
  return new Promise(resolve => {
    setTimeout(
      () => {
        resolve()
      },
      t || 3000
    )
  })
}

然後我們使用async/await文法，就可以輕松在循環中實作等待了：

const diff = async (el, oldChildren, newChildren) => {
  // ...
  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // ...
    handles.updatePointers(oldStartIdx, oldEndIdx, newStartIdx, newEndIdx)
    await wait()
  }
}

接下來我們新增兩個變量，來突出表示目前正在比較的兩個VNode：

// 目前比較中的節點索引
const currentCompareOldNodeIndex = ref(-1)
const currentCompareNewNodeIndex = ref(-1)

const handles = {
  // 更新目前比較節點
  updateCompareNodes(a, b) {
    currentCompareOldNodeIndex.value = a
    currentCompareNewNodeIndex.value = b
  }
}

<div
     class="nodeWrap"
     v-for="(item, index) in oldVNodeList"
     :key="item ? item.data.key : index"
     :class="{
         current: currentCompareOldNodeIndex === index,
     }"
     >
  <div class="node">{{ item ? item.children : '空' }}</div>
</div>
<div
     class="nodeWrap"
     v-for="(item, index) in newVNodeList"
     :key="item.data.key"
     :class="{
         current: currentCompareNewNodeIndex === index,
     }"
     >
  <div class="node">{{ item.children }}</div>
</div>

給目前比較中的節點添加一個類名，用來突出顯示，接下來還是一樣，需要在diff函數中調用該函數，但是，該怎麼加呢：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    if // ...
    } else if (isSameNode(oldStartVNode, newStartVNode)) {
      // ...
      oldStartVNode = oldChildren[++oldStartIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (isSameNode(oldStartVNode, newEndVNode)) {
      // ...
      oldStartVNode = oldChildren[++oldStartIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else if (isSameNode(oldEndVNode, newStartVNode)) {
      // ...
      oldEndVNode = oldChildren[--oldEndIdx]
      newStartVNode = newChildren[++newStartIdx]
    } else if (isSameNode(oldEndVNode, newEndVNode)) {
      // ...
      oldEndVNode = oldChildren[--oldEndIdx]
      newEndVNode = newChildren[--newEndIdx]
    } else {
      // ...
      newStartVNode = newChildren[++newStartIdx]
    }

我們想表現出頭尾比較的過程，其實就在這些if條件中，也就是要在每個if條件中停留一段時間，那麼可以直接這樣嗎：

const isSameNode = async () => {
  // ...
  handles.updateCompareNodes()
  await wait()
}

if (await isSameNode(oldStartVNode, newStartVNode))

很遺憾，我嘗試了不行，那麼隻能改寫成其他形式了：

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
  let stop = false
  let _isSameNode = false
  if (oldStartVNode === null) {
    callbacks.updateInfo('')
    oldStartVNode = oldChildren[++oldStartIdx]
    stop = true
  }
  // ...
  if (!stop) {
    callbacks.updateInfo('頭-頭比較')
    callbacks.updateCompareNodes(oldStartIdx, newStartIdx)
    _isSameNode = isSameNode(oldStartVNode, newStartVNode)
    if (_isSameNode) {
      callbacks.updateInfo(
        'key值相同，可以複用，進行patch打更新檔操作。新舊節點位置相同，不需要移動對應的真實DOM節點'
      )
    }
    await wait()
  }
  if (!stop && _isSameNode) {
    // ...
    oldStartVNode = oldChildren[++oldStartIdx]
    newStartVNode = newChildren[++newStartIdx]
    stop = true
  }
  // ...
}

我們使用一個變量來表示是否進入到了某個分支，然後把檢查節點是否能複用的結果也儲存到一個變量上，這樣就可以通過不斷檢查這兩個變量的值來判斷是否需要進入到後續的比較分支中，這樣比較的邏輯就不在if條件中了，就可以使用await了，同時我們還使用updateInfo增加了提示語：

const handles = {
  // 更新提示資訊
  updateInfo(tip) {
    info.value = tip
  }
}

接下來看一下節點的移動操作，當頭（oldStartIdx對應的oldStartVNode節點）尾（newEndIdx對應的newEndVNode節點）比較發現可以複用時，在打完更新檔後需要将oldStartVNode對應的真實DOM元素移動到oldEndVNode對應的真實DOM元素的位置，也就是插入到oldEndVNode對應的真實DOM的後面一個節點的前面：

if (!stop && _isSameNode) {
  // 頭-尾
  patchVNode(oldStartVNode, newEndVNode)
  // 把oldStartVNode節點移動到最後
  el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)
  // 更新指針
  oldStartVNode = oldChildren[++oldStartIdx]
  newEndVNode = newChildren[--newEndIdx]
  stop = true
}

那麼我們可以在insertBefore方法移動完真實的DOM元素後緊接着調用一下我們模拟清單的移動節點的方法：

if (!stop && _isSameNode) {
  // ...
  el.insertBefore(oldStartVNode.el, oldEndVNode.el.nextSibling)
  callbacks.moveNode(oldStartIdx, oldEndIdx + 1)
  // ...
}

我們要操作的實際上是代表真實DOM節點的actNodeList清單，那麼關鍵是要找到具體是哪個，首先頭尾的四個節點指針它們表示的是在新舊VNode清單中的位置，是以我們可以根據oldStartIdx和oldEndIdx擷取到oldVNodeList中對應位置的VNode，然後通過key值在actNodeList清單中找到對應的節點，進行移動、删除、插入等操作：

const handles = {
  // 移動節點
  moveNode(oldIndex, newIndex) {
    let oldVNode = oldVNodeList.value[oldIndex]
    let newVNode = oldVNodeList.value[newIndex]
    let fromIndex = findIndex(oldVNode)
    let toIndex = findIndex(newVNode)
    actNodeList.value[fromIndex] = '#'
    actNodeList.value.splice(toIndex, 0, oldVNode)
    actNodeList.value = actNodeList.value.filter(item => {
      return item !== '#'
    })
  }
}

const findIndex = (vnode) => {
  return !vnode
    ? -1
    : actNodeList.value.findIndex(item => {
        return item && item.data.key === vnode.data.key
      })
}

其他的插入節點和删除節點也是類似的：

插入節點：

const handles = {
  // 插入節點
  insertNode(newVNode, index, inNewVNode) {
    let node = {
      data: newVNode.data,
      children: newVNode.text
    }
    let targetIndex = 0
    if (index === -1) {
      actNodeList.value.push(node)
    } else {
      if (inNewVNode) {
        let vNode = newVNodeList.value[index]
        targetIndex = findIndex(vNode)
      } else {
        let vNode = oldVNodeList.value[index]
        targetIndex = findIndex(vNode)
      }
      actNodeList.value.splice(targetIndex, 0, node)
    }
  }
}

删除節點：

const handles = {
  // 删除節點
  removeChild(index) {
    let vNode = oldVNodeList.value[index]
    let targetIndex = findIndex(vNode)
    actNodeList.value.splice(targetIndex, 1)
  }
}

這些方法在diff函數中的執行位置其實就是執行insertBefore、removeChild方法的地方，具體可以本文源碼，這裡就不在具體介紹了。

另外還可以凸顯一下已經結束比較的元素、即将被添加的元素、即将被删除的元素等等，最終效果：

時間原因，目前隻實作了雙端diff算法的效果，後續會增加上快速diff算法的動畫過程，有興趣的可以點個關注喲~

倉庫：https://github.com/wanglin2/VNode_visualization。

我讓虛拟DOM的diff算法過程動起來了

繼續閱讀

diff函數

diff算法_雙線程跑傳統 diff 算法

React diff算法diff算法

React 之reconciliation--diff算法

如何在windows上将git diff配置成使用Beyond Compare

使用stablediffusion制作的第一個Ai真人模型，原型當然不能是别人，以後不怕總是被嫌棄說拍照拍的不好了@壹🟠

如果你有隻大貓，他會成為怎麼樣的夥伴呢？有了AI後，不會設計的我也有了一定的能力，把兒時的幻想具象化！Stabledif

Stable-diffusion 本地部署

iOS diff: /../Podfile.lock: No such file or directory~ 解決方法

接受自己的普通然後拼盡全力地去與衆不同Acceptyourcommonnessanddoyourbesttobediff

阿裡雲無需高深技術，搭建stable diffision平台實作AI文生圖自由

#ai繪畫#stablediffusion#美出進階感#midjourney#視覺

#ai繪畫#midjourney#stablediffusion#視覺#手機牆紙

父愛是高山，即使在最困難的時候，也鼓勵我挺直脊梁。Loveisamountain,eveninthemostdiffic

Git指令行筆記

如何在stable diffusion webui上使用最新的SDXL1.0? 支援哪些模型？