vue3-dom-diff算法

vue3diff算法

什么是vue3diff算法

Vue3中的diff算法是一種用于比較虛擬DOM樹之間差異的算法，其目的是為了高效地更新真實DOM，減少不必要的重渲染

主要過程

整個過程主要分為以下五步

前置預處理
后置預處理
僅處理新增
僅處理后置
處理包含新增、卸載、移動的復雜場景

第一步：前置預處理

首先定義一個變量i，記錄當前索引值
定義e1、e2記錄前置索引值
從前到后遍歷新舊索引列表
發現它們的節點值相同，則直接patch打補丁更新
否則跳出循環進入下一步。
vue3源碼：

    let i = 0const l2 = c2.lengthlet e1 = c1.length - 1 // prev ending indexlet e2 = l2 - 1 // next ending index// 1. sync from start// (a b) c// (a b) d ewhile (i <= e1 && i <= e2) {const n1 = c1[i]const n2 = (c2[i] = optimized? cloneIfMounted(c2[i] as VNode): normalizeVNode(c2[i]))if (isSameVNodeType(n1, n2)) {patch(n1,n2,container,null,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)} else {break}i++}

以下demo為例：

i=0 新舊節點都是n1 patch打補丁更新
i=1 新舊節點都是n2 patch打補丁更新
i=2 新節點n3!== n2 跳出循環
在這里插入圖片描述

第二步：后置預處理

從后到前去遍歷新舊索引列表
發現它們的節點相同，則直接patch
打更新
否則跳出循環
并記錄e1 e2的值

vue3源碼：

        // 2. sync from end// a (b c)// d e (b c)while (i <= e1 && i <= e2) {const n1 = c1[e1]const n2 = (c2[e2] = optimized? cloneIfMounted(c2[e2] as VNode): normalizeVNode(c2[e2]))if (isSameVNodeType(n1, n2)) {patch(n1,n2,container,null,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)} else {break}e1--e2--}

以下demo為例：

e1=6、e2=6對應都是n7節點，patch打補丁更新
e1=5、e2=5對應的新舊節點不同
跳出循環，記錄e1、e2的值

在這里插入圖片描述

第三步：處理僅有新增節點情況

當i > e1 并且i <= e2 ：代表僅有新增節點
則直接patch打補丁更新

vue3源碼：

     // 3. common sequence + mount// (a b)// (a b) c// i = 2, e1 = 1, e2 = 2// (a b)// c (a b)// i = 0, e1 = -1, e2 = 0if (i > e1) {if (i <= e2) {const nextPos = e2 + 1const anchor = nextPos < l2 ? (c2[nextPos] as VNode).el : parentAnchorwhile (i <= e2) {patch(null,(c2[i] = optimized? cloneIfMounted(c2[i] as VNode): normalizeVNode(c2[i])),container,anchor,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)i++}}}

以下demo為例：
i = 2時，新舊節點不同，從后往前遍歷
e1=2、e2=6對應都是n7節點，patch打補丁更新
e1=1、e2=5對應的新舊節點不同
這時i > e1 并且i <= e2，僅有新增節點，直接更新

在這里插入圖片描述

第四步：處理僅有卸載節點情況

當i > e2 并且i <= e1 ：代表僅有卸載節點
則直接卸載節點

vue3源碼：

     // 4. common sequence + unmount// (a b) c// (a b)// i = 2, e1 = 2, e2 = 1// a (b c)// (b c)// i = 0, e1 = 0, e2 = -1else if (i > e2) {while (i <= e1) {unmount(c1[i], parentComponent, parentSuspense, true)i++}}

以下demo為例：
i = 2時，新舊節點不同，從后往前遍歷
e1=2、e2=6對應都是n7節點，patch打補丁更新
e1=5、e2=1對應的新舊節點不同
這時i > e2 并且i <= e1 ，僅有卸載節點，直接卸載

在這里插入圖片描述

第五步：處理其他情況（新增、卸載、移動）

定義以下變量

變量	定義
s1	記錄舊節點列表要處理部分的起始位置
s2	記錄新節點列表要處理部分的起始位置
keyToNewIndexMap	新節點位置映射表；用于映射新節點與位置的映射關系
newIndexToOldIndexMap	新舊節點位置映射表；用于記錄新舊節點位置的映射關系。初始值為0，如果都是0，則判定為新節點，需要掛載
maxNewIndexSoFar	當前最遠位置；用于記錄新節點中當前的最遠位置。目的是用于判斷遍歷過程中是否呈現遞增趨勢。如果不是則代表產生了移動
moved	遞減趨勢，需要移動則標識為true;后續進行移動處理
j	最長遞增子序列位置

以下demo為列：
變動點：卸載n3 / 新增n8 / 移動n6

在這里插入圖片描述
當s1=2 : n3 ；在新節點位置映射表內沒有找到；則為卸載，把該節點移除
當s1=3: n4; 在新節點位置映射表中可以找到；則將s1 + 1 = 4放在新舊節點位置映射表中。同時對比新節點位置索引和最遠位置，3 > 0，則將新索引位置記錄到最遠位置中。最后打補丁更新
在這里插入圖片描述
當s1=4: n5; 在新節點位置映射表中可以找到；則將s1 + 1 = 5放在新舊節點位置映射表中。同時對比新節點位置索引和最遠位置，4 > 3，則將新索引位置記錄到最遠位置中。最后打補丁更新

當s1=5: n6; 在新節點位置映射表中可以找到；則將s1 + 1 = 6放在新舊節點位置映射表中。同時對比新節點位置索引和最遠位置，2 > 4，呈現遞減趨勢，說明位置發生了移動，則移動標識為true。最后patch打補丁更新
在這里插入圖片描述
到這一步已經遍歷完舊節點。這時候需要根據映射表找到最長遞增子序列
目的是為了讓節點做最小限度的移動操作
從下圖中新舊節點映射表中可以看出：最長遞增子序列索引值是4/5，將其記錄下來，對應的就是1/2
從后開始往前遍歷新舊節點映射表
定義變量 i 記錄當前新舊節點映射表位置，
定義變量 j 記錄最長遞增子序列位置，初始化為1
在這里插入圖片描述
當i=3：0 對應n8節點。0代表新增，掛載該節點
當i=2: 5 對應n5節點。j=1 對應最長遞增子序列。因此無需移動，直接跳轉
當i=1: 4 對應n4節點。j=2對應最長遞增子序列中。因此無需移動，直接跳轉
當i=0: 6對應n6節點。不處于最長遞增子序列當中。因此需要移動，執行移動操作
這樣下來，整個過程只需要掛載n8節點、卸載n3節點、移動n6節點，其他全部原地patch更新。性能得到了極大的保證

vue3源碼：

     // 5. unknown sequence// [i ... e1 + 1]: a b [c d e] f g// [i ... e2 + 1]: a b [e d c h] f g// i = 2, e1 = 4, e2 = 5else {const s1 = i // prev starting indexconst s2 = i // next starting index// 5.1 build key:index map for newChildrenconst keyToNewIndexMap: Map<PropertyKey, number> = new Map()for (i = s2; i <= e2; i++) {const nextChild = (c2[i] = optimized? cloneIfMounted(c2[i] as VNode): normalizeVNode(c2[i]))if (nextChild.key != null) {if (__DEV__ && keyToNewIndexMap.has(nextChild.key)) {warn(`Duplicate keys found during update:`,JSON.stringify(nextChild.key),`Make sure keys are unique.`,)}keyToNewIndexMap.set(nextChild.key, i)}}// 5.2 loop through old children left to be patched and try to patch// matching nodes & remove nodes that are no longer presentlet jlet patched = 0const toBePatched = e2 - s2 + 1let moved = false// used to track whether any node has movedlet maxNewIndexSoFar = 0// works as Map<newIndex, oldIndex>// Note that oldIndex is offset by +1// and oldIndex = 0 is a special value indicating the new node has// no corresponding old node.// used for determining longest stable subsequenceconst newIndexToOldIndexMap = new Array(toBePatched)for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0for (i = s1; i <= e1; i++) {const prevChild = c1[i]if (patched >= toBePatched) {// all new children have been patched so this can only be a removalunmount(prevChild, parentComponent, parentSuspense, true)continue}let newIndexif (prevChild.key != null) {newIndex = keyToNewIndexMap.get(prevChild.key)} else {// key-less node, try to locate a key-less node of the same typefor (j = s2; j <= e2; j++) {if (newIndexToOldIndexMap[j - s2] === 0 &&isSameVNodeType(prevChild, c2[j] as VNode)) {newIndex = jbreak}}}if (newIndex === undefined) {unmount(prevChild, parentComponent, parentSuspense, true)} else {newIndexToOldIndexMap[newIndex - s2] = i + 1if (newIndex >= maxNewIndexSoFar) {maxNewIndexSoFar = newIndex} else {moved = true}patch(prevChild,c2[newIndex] as VNode,container,null,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)patched++}}// 5.3 move and mount// generate longest stable subsequence only when nodes have movedconst increasingNewIndexSequence = moved? getSequence(newIndexToOldIndexMap): EMPTY_ARRj = increasingNewIndexSequence.length - 1// looping backwards so that we can use last patched node as anchorfor (i = toBePatched - 1; i >= 0; i--) {const nextIndex = s2 + iconst nextChild = c2[nextIndex] as VNodeconst anchor =nextIndex + 1 < l2 ? (c2[nextIndex + 1] as VNode).el : parentAnchorif (newIndexToOldIndexMap[i] === 0) {// mount newpatch(null,nextChild,container,anchor,parentComponent,parentSuspense,namespace,slotScopeIds,optimized,)} else if (moved) {// move if:// There is no stable subsequence (e.g. a reverse)// OR current node is not among the stable sequenceif (j < 0 || i !== increasingNewIndexSequence[j]) {move(nextChild, container, anchor, MoveType.REORDER)} else {j--}}}}