Vue中的Diff算法的學習與研究

今天來分享一下 Vue 中經常聽聞的 Diff 算法相關知識。

可能還有一些朋友不太了解 Diff 算法是什麼、有什麼用，我們接下來先大致介紹一下 diff 算法在 Vue3 中的作用等相關知識，方便沒有基礎的同學能夠盡量的看懂這篇文章。

如果你已經大致知道了相關前置知識，那就直接跳過這部分前往下面文章看一看 patch 最小量化更新（即 diff 算法）的歷程吧。

本篇文章盡可能的減少代碼，更多的圖片動畫演示，我們從一張張思路圖來探討研究前輩們的智慧結晶。

介紹#

在 Vue 中採用的虛擬 VNode 進行對比然後進行掛載 / 更新 / 卸載操作，其中最為主要的就是更新操作，更新操作的效率會影響到渲染頁面更新量，越接近於編譯時框架所帶來的更新量性能就會越高，為了盡量讓 Vue 這個編譯時 + 運行時的框架帶來的更新量最小化，於是就帶來了Diff 算法用於檢測兩棵新舊節點樹之間最小的差異，以帶來最少的更新量，提升頁面性能。

目前在《Vue.js 設計與實現》中Diff 算法僅限在新舊節點都存在key，並未提及在無 key時該如何減少 patch 的最小量化，key可用作元素的唯一標識用作新舊節點對比。

接下來我們將隨著一步步的代碼與思路的演進，領略從更新操作中的性能提升，從簡單粗暴到複雜優雅。

直接#

最為簡單粗暴的做法就是我們根本不去關注新舊節點中存不存在差異，直接把舊節點全部卸載，把新節點重新掛載到容器內，這樣就完成了更新的操作。這種方式甚至不需要被稱為Diff了，因為根本不關心差異化，無腦卸載掛載即可。如下圖可見在這樣直接全卸載然後全掛載的操作，直接粗暴但是簡單，但性能距離命令式代碼差距過大，有不需要卸載只需要簡單移動節點位置即可達成目標的節點處理方法卻仍然進行卸載重新掛載操作，於是開啟了我們對於此類算法的思考，為了更高的性能而進行苦思冥想的追尋之旅～

全卸載 7 全掛載執行示意圖

圖 0-1 全卸載 & 全掛載

簡單#

緣起#

相較於全卸載 & 全掛載這樣粗暴的流程，我們首先可以很清楚的看出一個問題，對於可復用節點的衡量。我們可以觀測下圖 1-1新舊兩組節點

圖 1-1 新舊兩顆樹的對比圖

我們可以很明顯發現，有部分節點只需要非常簡單移動，有部分節點只需要更新文本內容差異，有的只需要把多餘的舊節點卸載或者把多出來的新節點進行掛載操作即可。

復用與 key#

那麼我們該怎麼去對比新舊兩顆樹的節點是否相同呢？苦思冥想中，Vue 給了我們答案，為節點新增屬性key當作節點的唯一值，相當於節點的身份證一樣的存在。

圖 1-2 有 key 與無 key 時節點比較情況

這樣我們在比較節點時才有了依據才可以避免無腦全卸載 & 全掛載這樣的操作，進而真正開始diff算法的探究過程中。

現在我們已經主觀層規定了這種節點列表中的每個節點都有著一個唯一key，那麼我們下一步就可以開始處理dom節點的復用。

接下來我們重新觀察一下圖 1-1這對新舊節點樹，看一看我們都需要怎麼做才能盡可能少的操作 dom。

我們發現這對新舊節點樹中發現了以下幾種情況：

p-1、p-2、p-3、p-4 節點可與舊節點進行復用
p-5 節點需要卸載
p-6 節點需要掛載
節點有可能需要進行節點位置移動

接下來我們要做的其實很簡單，大致克對應著上面的情況進行處理：

根據新樹去查看舊樹上是否有key 同值的節點，如果有則先進行一次打補丁操作，
如果新書的某個節點在舊樹中找不到可復用的節點則說明這是一個需要掛載的新節點
如果舊樹的某個節點在新樹中找不到相應的節點（即沒有被復用）則說明這是一個需要卸載的舊節點
對需要移動的節點進行移動

/**
 * 簡單Diff算法
 * @param oldVNode 舊節點列表
 * @param vNode 新節點列表
 * @param container 節點列表掛載容器
 */
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
    for (let i = 0; i < vNode.length; i++) {
        let findLock = false; // 標識這個新節點是否找到可復用的舊節點
        for (let j = 0; j < oldVNode.length; j++) {
            if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) { // 根據唯一key來尋找可復用的元素
                findLock = true; // 找到可復用節點
              	// 這一步會同步old節點的element至new節點的element屬性
                patch(oldVNode[j], vNode[i], container); 
              	// ??? 節點是否需要移動，應該移動到哪裡
                break;
            };
        }
        if (!findLock) {
            // 執行到這裡說明沒有找到可復用的節點，需要新建節點並進行插入操作
            // patch(null, vNode[i], container, ???); 插入元素錨地的位置
        }
    };
    // 遍歷舊樹, 查找到需要卸載的節點進行卸載操作
    oldVNode.forEach(oldElement => {
        if (!vNode.find(newElement => newElement.key === oldElement.key)) {
            unMountElement(oldElement);
        };
    });
};

這幾個步驟處理中難點就是節點移動，該怎麼移動，移動到哪個節點前面？新節點掛載該掛載哪個位置？著同樣也是 diff 過程中非常重要的一步。

移動#

接下來我們結合圖 1-2觀察一下我們究竟該怎麼去移動 / 掛載元素。如圖圖 1-3

圖 1-3 新舊虛擬節點與真實節點

是否感覺出來有點雜亂無章呢，這裡的移動元素錨點位置究竟是哪些呢？我們不妨回過頭去逆向思維思考一下，去考慮一下在什麼情況下節點不需要移動呢，答案就是新舊兩組節點列表的順序保持不變，保持不變則代表著每次新節點列表前往舊節點列表中去找到可復用節點時的舊節點的索引是呈現一個遞增的趨勢。

例如結合圖 1-2就能很明顯看出找到的舊節點索引趨勢為 [0, 1, 2, 3, 4]。

我們在結合圖 1-3來看找到的舊節點索引趨勢為 [3, 2, -1, 0, 1]，（此處我們暫時對新掛載的節點找到的舊節點索引值表示為 **-1**，但在實際的移動過程中，新掛載的節點根本不會進入到趨勢計算中），好了，回到我們找到的舊節點索引趨勢來看，能夠看出 p-4 在舊節點中索引為 3，p-3 在舊節點索引為 2，這我們可以得到一個結論，說明在新節點中 p-3 節點是需要移動的，p-3 的真實元素位置是位於 p-4 真實元素位置之後的，以此類推，在這個例子中所有新的節點都在 p-4 的後面，我們都是以 p-4 的舊索引位為基準進行比對，但在更大的例子中就需要我們不斷的去更新基準（遞增趨勢的截止處索引），去不斷的判定這個節點是否需要移動。

為了更加方便、直接、全面、快速的帶著大家感受這個移動過程，我們可以看下這個代碼執行動畫演示圖 1-4。

簡單 Diff 算法執行示意圖

圖 1-4 節點移動執行全流程動畫演示圖

/**
 * 簡單Diff算法
 * @param oldVNode 舊節點列表
 * @param vNode 新節點列表
 * @param container 節點列表掛載容器
 */
function simpleDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
    let lastMaxIndex = 0; // 當前最大舊索引值
    for (let i = 0; i < vNode.length; i++) {
        let findLock = false;
        for (let j = 0; j < oldVNode.length; j++) {
            if ((typeof vNode[i].key !== "undefined") && vNode[i].key === oldVNode[j].key) {
                // ***省略patch代碼***
                if (j < lastMaxIndex) { // 需要移動
                    const prevElement = vNode[i - 1];
                    if (prevElement) {
                        insertElement(container, oldVNode[j]._element, prevElement._element?.nextSibling ?? null);
                    };
                } else {
                    lastMaxIndex = j;
                }
                break;
            };
        }
        if (!findLock) {
            // 執行到這裡說明沒有找到可復用的節點，需要新建節點並進行插入操作，錨點位同上的邏輯一致
            const prevElement = vNode[i - 1];
            patch(null, vNode[i], container, prevElement?._element?.nextSibling ?? null);
        }
    };
    // ***省略節點卸載代碼***
};

雙端#

緣起#

在簡單 diff 算法中，我們有時候會在一些例子中有發現更加快捷的步驟，如下圖

圖 2-1 特殊的例子

我們發現如果按照簡單 diff 算法的執行流程，需要先把 p-1 移動至 p-3 元素後方，然後在把 p-2 移動至 p-1 元素後方，但是我們人眼來觀察這對新舊節點列表，發現明明我只需要把 p-3 移動至 p-1 節點的前方即可，如圖 2-2明明一步就能解決的方式卻在 diff 算法中需要兩次移動節點。

圖 2-2 在一些情況下移動 Dom 次數更少的處理

思想#

現在可優化點出來了，我們就要想着該怎麼去優化了，在雙端 diff 算法思想中，分別為新舊節點列表都建立相應的頭尾索引，並分別將 4 個索引處指向的 VNode 進行比對並不斷的移動相應的索引。如圖 2-3

圖 2-3 雙端索引與對比指示圖

會發現在一些情況下確實能夠通過這四次的對比然後移動相應的索引，能夠在頭尾處找到key 同值需要處理的節點。例如圖 2-3的例子，我們先不去思考如果 (p-3<=>p-1、p-2<=>p-3、p-3<=>p-3、p-2<=>p-1) 這四次對比沒找到同key的情況，這種情況我們後續在進行處理，我們先思考加入遇見了這種情況，我們該怎麼去移動節點？

移動#

newVNode[newStartIndex].key === oldVNode[oldStartIndex].key

當相等的情況下，意味著節點無需移動，只需要進行 patch 補丁操作即可，然後把newStartIndex與oldStartIndex向後移動即可。
newVNode[newEndIndex].key === oldVNode[oldEndIndex].key

當相等的情況下，意味著節點無需移動，只需要進行 patch 補丁操作即可，然後把newEndIndex與oldEndIndex向前移動即可。
newVNode[newEndIndex].key === oldVNode[oldStartIndex].key

原先位於舊節點列表頭索引位置，現在要移動至新節點列表尾索引位置，說明在這次對比中原本在舊節點列表中頭部現在在新節點列表中的尾部，表明節點需要移動，把節點移動至oldVNode[oldEndIndex]的下一位即可，然後把參與到這輪使用的索引進行正確的更新，newEndIndex向前移動，oldStartIndex向後移動。
newVNode[newStartIndex].key === oldVNode[oldEndIndex].key

原先位於舊節點列表尾索引位置，現在要移動至新節點列表的頭索引位置，說明在此次對比中原本在舊節點列表中尾部的元素現在在新節點列表中的頭部，表明節點需要移動，把節點移動至oldVNode[oldStartIndex]的上一位即可，即頭部，然後正確更新參與索引，newStartIndex向後移動，oldEndIndex向前移動。

現在我們已經把情況判定完畢了，以及處理了特殊的情況，但是在一些更特殊的例子，上方節點量不同的情況下會發生一邊已經oldStartIndex > oldEndIndex終止掉循環了，或者一邊newStartIndex > newEndIndex終止掉循環了，造成節點多的那一方出現節點未卸載 / 未掛載情況，我們發現這種情況始終是單邊的，於是我們可以總結出一定的規律，為while循環的終止做出兜底。

同簡單 diff 算法一樣，在這裡我同樣會給到一個代碼執行動畫演示，幫助我們可視化理解雙端 Diff，參見下圖 2-5

雙端 Diff 算法執行示例流程圖

圖 2-5 雙端 diff 執行流程示意圖

/**
 * 雙端diff算法
 * @param oldVNode 
 * @param vNode 
 * @param container 
 */
function doubleEndedDiff(oldVNode: (VNode | undefined)[], vNode: VNode[], container: ContainerElement) {
    let oldStartIndex = 0;
    let newStartIndex = 0;
    let oldEndIndex = oldVNode.length - 1;
    let newEndIndex = vNode.length - 1;
    while (oldStartIndex <= oldEndIndex && newStartIndex <= newEndIndex) {
        const oldStartVNode = oldVNode[oldStartIndex];
        const oldEndVNode = oldVNode[oldEndIndex];
        const newStartVNode = vNode[newStartIndex];
        const newEndVNode = vNode[newEndIndex];
        // 預防舊節點被操作為undefined情況
        if (!oldStartVNode) {
            oldStartIndex++;
            continue;
        }
        if (!oldEndVNode) {
            oldEndIndex--;
            continue;
        }
        // 四種對比移動節點情況
        if (oldStartVNode.key === newStartVNode.key) {
            patch(oldStartVNode, newStartVNode, container)
            oldStartIndex++;
            newStartIndex++;
        } else if (oldEndVNode.key === newEndVNode.key) {
            patch(oldEndVNode, newEndVNode, container);
            oldEndIndex--;
            newEndIndex--;
        } else if (oldStartVNode.key === newEndVNode.key) {
            patch(oldStartVNode, newEndVNode, container);
            insertElement(container, oldStartVNode._element, oldEndVNode._element?.nextSibling);
            oldStartIndex++;
            newEndIndex--;
        } else if (oldEndVNode.key === newStartVNode.key) {
            // 打補丁
            patch(oldEndVNode, newStartVNode, container);
            insertElement(container, oldEndVNode._element, oldStartVNode._element);
            // 移動索引
            oldEndIndex--;
            newStartIndex++;
        } else {
            // 找到舊節點中與新節點相同key的節點
            const findOldIndex = oldVNode.findIndex(node => node && node.key === newStartVNode.key);
            if (findOldIndex > 0) {
                // 打補丁
                patch(oldVNode[findOldIndex]!, newStartVNode, container);
                insertElement(container, oldVNode[findOldIndex]!._element, oldStartVNode._element);
                oldVNode[findOldIndex] = undefined;
                newStartIndex ++;
            } else { // 說明這個newStartVNode是一個新增節點
                patch(null, newStartVNode, container, oldStartVNode._element);
                newStartIndex++;
            }
        }
    }
    // 舊節點已經循環完畢，但新節點中有剩餘，需要把這些剩餘的新節點進行掛載操作
    if (oldEndIndex < oldStartIndex && newStartIndex <= newEndIndex) {
        for (let i = newStartIndex; i <= newEndIndex; i++) {
            patch(null, vNode[i], container, vNode[i - 1]?._element?.nextSibling);
        }
    } else if(newEndIndex < newStartIndex && oldStartIndex <= oldEndIndex) {
        for (let i = oldStartIndex; i <= oldEndIndex; i++) {
            oldVNode[i] && unMountElement(oldVNode[i]!);
        }
    }
}

快速#

緣起#

使用雙端 diff 算法時的 vue 在進行js-framework-benchmark進行跑分實測時注意到，ivi與inferno所採用的快速 diff快速性能會稍優於使用雙端 diff的 vue，有必要去了解借鑒其思路與經驗，為提高性能而努力。

圖 3-1 ivi,inferno,vue,react 實測性能對比

雜談一些八卦，之前聽過一些人吐槽 react 性能慢是因為 react 內部對虛擬 node 的數據結構為一個自行設計的類單鏈表結構，造成 react 是不能使用雙端 diff 這樣的算法的，只能單向尋找 diff，有的開發者借鑒 react 的思想，摒棄其自行設計的數據結構，採用了雙端 diff 後性能有明顯提升。例如Unis。

思想#

有這樣一種場景，元素的前置節點與後置節點相同，只有中間部分元素不盡相同，這時候有個十分類似的思想算法處理叫 **“純文本 diff”**，該算法主要用在純文本上，如下圖 3-1。

圖 3-1 純文本 diff 思想示例

我們發現，在這兩段新舊文字中，只有中間的div發生了變化，邊為了文字input。那麼這種思想是否能夠幫助我們處理新舊節點列表呢？我們觀察下面這個例子如圖 3-2。

圖 3-2 應用純文本 diff 思想的例子

我們發現好像優先去處理相同的前置節點（即newVNode[startIndex] === oldVNode[startIndex]）與相同的後置節點（newVNode[endIndex] === oldVNode[endIndex]），然後在單獨去處理中間雜亂的節點似乎是一個好的選擇，這樣可以避免在遇見只需要更新操作的節點時卻還需要考量當前新節點是否需要移動等。

但是又思考了思考，貌似只從這個思想優化點方面就能提升那麼多的性能麼，感覺有點不可置信呀。當然，在快遞 diff 算法中還引進的了個概念最長遞增子序列，引進該概念的作用是為了更加高效的處理除了相同的前後置節點外的其餘節點，幫助其進行移動等操作，參見下圖 3-3。

快速 diff 算法節點移動執行示意圖

圖 3-3 快速 diff 算法節點移動執行示意圖

移動#

我們看完上圖後會發現有個關鍵點就是source這個怎麼來？source用於記錄新節點在舊節點中相應的索引，我們通常或通過雙重for循環達到這樣的效果形成source，但是這樣有個缺點就是時間複雜度高，達到了O(n^2)，數據量越大表明耗時越是雙倍變多。

const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新舊節點位置映射
let moved = false;
let pos = 0;
// 雙層for時間複雜度高, O(n^2)
for (let i = startIndex; i <= newEndIndex; i++) {
    for (let j = startIndex; j <= oldEndIndex; j++) {
        if (vNode[i].key === oldVNode[j].key) { // 找到新舊節點映射點
            patch(oldVNode[j], vNode[i], container);
            source[i - startIndex] = j;
            if (j < pos) { // 定位在新節點樹中的最大索引處, 可用來確定是否需要移動節點這一步
                moved = true;
            } else {
                pos = j;
            }
            break;
        }
    }
}
// 循環舊節點列表進行卸載沒被復用的節點
oldVNode.forEach(oldElement => {
    if (!vNode.find(newElement => newElement.key === oldElement.key)) {
        unMountElement(oldElement);
    };
});

時間複雜度是算法中必須掌握的一項基礎，用於大致表示一段算法的耗時。與其相應經常結伴出現的就是空間複雜度，空間複雜度主要用於大致表示一段算法所需要 / 消耗的內存大小，在現在的時代內存容量完全能夠支撐，所以在為了降低時間複雜度時經常的做法就是空間換時間，意思是用更多的內存以降低時間複雜度。

我們回過頭再看上面這段代碼，有沒有似曾相識的感覺，yes，就是簡單 Diff 算法，除了沒有移動節點和新增節點的功能，其他的都基本一致，接下來我們觀察下面這段優化後代碼。

const newVNodePatchCount = newEndIndex - startIndex + 1;
const source = new Array(newVNodePatchCount).fill(-1); // 新舊節點位置映射
let moved = false;
let pos = 0;
const keySourceMap: Record<number | string | symbol, number> = {};
for (let i = startIndex; i <= newEndIndex; i++) {
    keySourceMap[vNode[i].key!] = i; // 利用唯一key+數組存留來關聯上新舊兩棵樹的差異對比
}
for (let i = startIndex; i <= oldEndIndex; i++) {
    const sourceKey = keySourceMap[oldVNode[i].key!];
    if (sourceKey !== undefined) { // 說明有可復用節點
        patch(oldVNode[i], vNode[sourceKey], container); // 打補丁操作
        source[sourceKey - startIndex] = i; // 新舊節點同key映射點
        if (sourceKey < pos) { // 定位在新節點樹中的最大索引處, 可用來確定是否需要移動節點這一步
            moved = true;
        } else {
            pos = sourceKey;
        }
    } else { // 沒找到說明這個舊節點是需要卸載的
        unMountElement(oldVNode[i]);
    };
}

發現原來的O(n^2)的雙for循環時間複雜度已經被成功把拆分開了，時間複雜度降低為O(n)，但是發現多出來了個變量叫做ketSourceMap，這就是我們在處理時採用到的空間換時間的優化做法。

現在接下來就是根據source計算出最長遞增子序列，我們在這裡去考慮為什麼會需要最長遞增子序列，最長遞增子序列是一個遞增的列表項，說明這個最長遞增子序列的節點順序正確並且不需要節點移動，這樣移動節點的次數會是最少的，這就是最長遞增子序列在此處最大的作用。

接下來，同我們之前一樣，我會給到一個快速 diff 的代碼執行示意動畫，請看下圖 3-4。

快速 diff 算法執行示意圖

圖 3-4 快速 diff 算法執行流程示意圖

/**
 * 快速diff算法
 * @param oldVNode 
 * @param vNode 
 * @param container 
 */
function fastDiff(oldVNode: VNode[], vNode: VNode[], container: ContainerElement) {
    let startIndex = 0;
    while(oldVNode[startIndex] && vNode[startIndex] && oldVNode[startIndex]?.key === vNode[startIndex]?.key) { // 前置節點檢查
        patch(oldVNode[startIndex], vNode[startIndex], container);
        startIndex ++;
    };
    let oldEndIndex = oldVNode.length - 1;
    let newEndIndex = vNode.length - 1;
    // 如果前置節點已經把新節點/舊節點中某一列觀測完畢了，則沒有必要在去後置節點檢查了，如果沒有這層檢測反而為引起預期之外的渲染情況
    if ((startIndex !== oldVNode.length) || (startIndex !== vNode.length)) {
        while(oldVNode[oldEndIndex] && vNode[newEndIndex] && oldVNode[oldEndIndex].key === vNode[newEndIndex].key) { // 後置節點檢查
            patch(oldVNode[oldEndIndex], vNode[newEndIndex], container);
            oldEndIndex--;
            newEndIndex--;
        };
    }
    if (newEndIndex >= startIndex && oldEndIndex < startIndex) { // 說明舊節點已經排查完畢但新節點中還存在著未被排查的節點
        for (let i = startIndex; i <= newEndIndex; i++) {
            patch(null, vNode[i], container, vNode[newEndIndex + 1]?._element); // 掛載
        }
    } else if (newEndIndex < startIndex && oldEndIndex >= startIndex) { // 說明新節點已經排查完畢但舊節點中還存在著未被排查
        for (let i = startIndex; i <= oldEndIndex; i++) {
            unMountElement(oldVNode[i]); // 卸載
        }
    } else { // 說明新舊節點中同時存在著未被掛載/卸載掉節點
        // doubleEndedDiff(oldVNode.slice(startIndex, oldEndIndex + 1), vNode.slice(startIndex, newEndIndex + 1), container);
        const newVNodePatchCount = newEndIndex - startIndex + 1;
        const source = new Array(newVNodePatchCount).fill(-1); // 新舊節點位置映射
        let moved = false;
        let pos = 0;
        // 雙層for時間複雜度高, O(n^2)
        // for (let i = startIndex; i <= newEndIndex; i++) {
        //     for (let j = startIndex; j <= oldEndIndex; j++) {
        //         if (vNode[i].key === oldVNode[j].key) { // 找到新舊節點映射點
        //             patch(oldVNode[j], vNode[i], container);
        //             source[i - startIndex] = j;
        //             if (j < pos) { // 定位在新節點樹中的最大索引處, 可用來確定是否需要移動節點這一步
        //                 moved = true;
        //             } else {
        //                 pos = j;
        //             }
        //             break;
        //         }
        //     }
        // }
        // // 循環舊節點列表進行卸載沒被復用的節點
        // oldVNode.forEach(oldElement => {
        //     if (!vNode.find(newElement => newElement.key === oldElement.key)) {
        //         unMountElement(oldElement);
        //     };
        // });

        // 空間換時間，降低時間複雜度，O(n)
        const keySourceMap: Record<number | string | symbol, number> = {};
        for (let i = startIndex; i <= newEndIndex; i++) {
            keySourceMap[vNode[i].key!] = i; // 利用唯一key+數組存留來關聯上新舊兩棵樹的差異對比
        }
        for (let i = startIndex; i <= oldEndIndex; i++) {
            const sourceKey = keySourceMap[oldVNode[i].key!];
            if (sourceKey !== undefined) { // 說明有可復用節點
                patch(oldVNode[i], vNode[sourceKey], container); // 打補丁操作
                source[sourceKey - startIndex] = i; // 新舊節點同key映射點
                if (sourceKey < pos) { // 定位在新節點樹中的最大索引處, 可用來確定是否需要移動節點這一步
                    moved = true;
                } else {
                    pos = sourceKey;
                }
            } else { // 沒找到說明這個舊節點是需要卸載的
                unMountElement(oldVNode[i]);
            };
        }
        if (moved) {
            // 計算出最長遞增子序列
            const result = getSequence(source);
            let longestLastIndex = result.length - 1; // 最長遞增子序列的最後一位索引
            let newLastIndex = newEndIndex - startIndex; // 新節點列表以startIndex為基準索引開始的最後一位索引值
            for (let i = newLastIndex; i >= 0; i--) { // 反向循環
                if (source[i] === -1) { // 說明這個節點是新增節點
                    const currentVNode = vNode[i + startIndex];
                    patch(null, currentVNode, container, vNode[i + startIndex + 1]?._element); // 以新節點的當前位的下個節點為錨點位進行插入
                } else if (i !== result[longestLastIndex]) { // 不是最長遞增子序列，節點需要移動
                    // 節點都被patch打補丁過了（element屬性也被同步過了），只需要考慮移動節點即可，錨點位置仍然按照上面新增節點那樣處理即可
                    const currentVNode = vNode[i + startIndex];
                    insertElement(container, currentVNode._element, vNode[i + startIndex + 1]?._element);
                } else { // 說明遇見了最長遞增子序列，該節點不需要移動，longestLastIndex索引向前移動
                    longestLastIndex--;
                }
            }
        };
    }
};

參考資料#

《Vue.js 設計與實現》第七、八、九、十、十一章內容