Vue 3.0 diff 算法及原理
轉(zhuǎn)自：GitHub - liuhanqu
Vue 3.0 采取的 diff 算法和 2.0 的雙端比較有點(diǎn)不同。大概的原理如下
// c1: a b [ c d e ] f g
// c2: a b [ d e c h ] f g
假如有如上的 c1 和 c2 新舊 children，在 diff 的時(shí)候，會(huì)有一個(gè)預(yù)處理的過程。
先從前往后比較，當(dāng)節(jié)點(diǎn)不同時(shí)，不再往后進(jìn)行比較。接著又從后往前進(jìn)行比較，當(dāng)節(jié)點(diǎn)不同時(shí)，不再往前進(jìn)行比較。
經(jīng)過預(yù)處理之后，c1 和 c2 真正需要進(jìn)行 diff 的部分如下所示：
// c1: c d e
// c2: d e c h
最后利用 “最長(zhǎng)遞增子序列”，完成上述差異部分的比較，提高 diff 效率。
處理相同的前后節(jié)點(diǎn)
預(yù)處理過程代碼如下所示：
const patchKeyedChildren = (
c1,
c2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
) => {
let i = 0;
const l2 = c2.length
let e1 = c1.length - 1
let e2 = c2.length - 1
// 1. sync from start
while (i <= e1 && i <= e2) {
const n1 = c1[i]
const n2 = c2[i]
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
i++
}
// 2. sync from end
while (i <= e1 && i <= e2) {
const n1 = c1[e1]
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
patch(
n1,
n2,
container,
parentAnchor,
parentComponent,
parentSuspense,
isSVG,
optimized
)
} else {
break
}
e1--
e2--
}
}
僅有節(jié)點(diǎn)新增或移除
進(jìn)行預(yù)處理還有一個(gè)好處，就是在某些情況下，我們可以明確的知道有節(jié)點(diǎn)的新增或者刪除。
節(jié)點(diǎn)新增
i、e1、e2 滿足下述關(guān)系時(shí)，可以認(rèn)為是有節(jié)點(diǎn)新增
// 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 = 0
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1;
const anchor = nextPos < l2 ? c2[nextPos] : parentAnchor
while (i <= e2) {
patch(
null,
c2[i],
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
i++
}
}
} else if {
//
} else {
//
}
節(jié)點(diǎn)移除
i、e1、e2 滿足下述關(guān)系時(shí)，可以認(rèn)為是有節(jié)點(diǎn)被移除
// 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 = -1
if (i > e1) {
//
} else if (i > e2) {
while (i <= e1) {
unmount(c1[i], parentComponent, parentSuspense, true)
i++
}
} else {
//
}
有節(jié)點(diǎn)移動(dòng)、新增或刪除
有時(shí)候情況可能沒有上述那么地簡(jiǎn)單，即 i、e1、e2 并不滿足上述兩種情形時(shí)，我們就要尋找其中需要被移除、新增的節(jié)點(diǎn)，又或是判斷哪些節(jié)點(diǎn)需要進(jìn)行移動(dòng)。
為此，我們需要去遍歷 c1 中還沒有進(jìn)行處理的節(jié)點(diǎn)，然后查看在 c2 中是否有對(duì)應(yīng)的節(jié)點(diǎn)（key 相同）。沒有，則說明該節(jié)點(diǎn)已經(jīng)被移除，那就執(zhí)行 unmount 操作。
首先，為了快速確認(rèn) c1 的節(jié)點(diǎn)在 c2 中是否有對(duì)應(yīng)的節(jié)點(diǎn)及所在的位置，對(duì) c2 中的節(jié)點(diǎn)建立一個(gè)映射 （key: index）
// 5. unknown sequence
// [i ... e1 + 1]: a b [c d e] f g
// [i ... e2 + 1]: a b [d e c h] f g
// i = 2, e1 = 4, e2 = 5
if (i > e1) {
//
} else if (i > e2) {
//
} else {
const s1 = i
const s2 = i
const keyToNewIndexMap = new Map()
// 5.1 build key:index map for newChildren
for (i = s2; i <= e2; i++) {
const nextChild = c2[i]
if (nextChild.key !== null) {
keyToNewIndexMap.set(nextChild.key, i)
}
}
}
接著，定義以下幾個(gè)變量
let j
let patched = 0
const toBePatched = e2 - s2 + 1 // c2 中待處理的節(jié)點(diǎn)數(shù)目
let moved = false
// used to track whether any node has moved
let maxNewIndexSoFar = 0 // 已遍歷的待處理的 c1 節(jié)點(diǎn)在 c2 中對(duì)應(yīng)的索引最大值
// 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 subsequence
const newIndexToOldIndexMap = new Array(toBePatched) // 用于后面求最長(zhǎng)遞增子序列
for (i = 0; i < toBePatched; i++) {
newIndexToOldIndexMap[i] = 0
}
然后，遍歷 c1 中待處理的節(jié)點(diǎn)，判斷否 c2 中是有相同 key 的節(jié)點(diǎn)存在。
沒有，說明該節(jié)點(diǎn)已經(jīng)被移除，unmount。 有，調(diào)用 patch 函數(shù)。并記錄節(jié)點(diǎn)在 c1 中的索引。同時(shí)，記錄節(jié)點(diǎn)在 c2 中的最大索引，假如節(jié)點(diǎn)在 c2 中的索引位置小于這個(gè)最大索引，那么說明是有元素需要進(jìn)行移動(dòng)。
// 5.2 loop through old children left to be patched and try to patch
// matching nodes & remove nodes that are no longer present
for (i = s1; i <= e1; i++) {
const prevChild = c1[i]
// (A)
let newIndex
if (prevChild.key !== null) {
newIndex = keyToNewIndexMap.get(prevChild.key)
} else {
for (j = s2; i <= e2; j++) {
if (
newIndexToOldIndexMap[j - s2] === 0 &&
isSameVNodeType(prevChild, c2[j])
) {
newIndex = j
break
}
}
}
if (newIndex === void 0) {
unmount(prevChild, parentComponent, parentSuspense, true)
} else {
newIndexToOldIndexMap[newIndex - s2] = i + 1 // (B)
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
patch(
prevChild,
c2[i],
container,
null,
parentComponent,
parentSuspense,
isSVG,
optimized
)
patched++ // (C)
}
}
是不是 c1 中的所有節(jié)點(diǎn)都需要在 c2 中尋找對(duì)應(yīng)節(jié)點(diǎn)，然后調(diào)用 patch 呢。
注意到上面的代碼 (C)，我們會(huì)更新已經(jīng) patched 的節(jié)點(diǎn)的數(shù)目，那么當(dāng) patched > toBePatched，可以認(rèn)為接下來遍歷的 c1 中的節(jié)點(diǎn)都是多余的了，直接移除就好。
所以在上面的 (A) 處需要補(bǔ)充一下代碼
if (patched >= toBePatched) {
// all new children have been patched so this can only be a removal
unmount(prevChild, parentComponent, parentSuspense, true)
continue
}
到這里，就是較難理解的部分了。
開篇我們說過，預(yù)處理過后，剩下的節(jié)點(diǎn)會(huì)借助最長(zhǎng)遞增子序列來提高 diff 效率。
求解最長(zhǎng)遞增子序列，主要的目的就是為了減少 dom 元素的移動(dòng)，也可以理解為最少的 dom 操作。
首先，我們需要求解得到最長(zhǎng)遞增子序列
// generate longest stable subsequence only when nodes have moved
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
先看看這里的 newIndexToOldIndexMap 的值是什么。
結(jié)合一下具體的例子，假設(shè) c1 、c2 如下圖所示
定義并初始化 newIndexToOldIndexMap
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) {
newIndexToOldIndexMap[i] = 0
}
toBePatched 即預(yù)處理后，c2 中待處理的節(jié)點(diǎn)數(shù)目。對(duì)應(yīng)這里的例子，會(huì)有
toBePatched = 4
newIndexToOldIndexMap = [0, 0, 0, 0]
注意到上面 5.2 遍歷 c1 中節(jié)點(diǎn)的代碼的 (B) 處，有
// 這里是 i + 1，不是 i
// 因?yàn)?nbsp;0 是一個(gè)特殊值，表示這個(gè)是新增的節(jié)點(diǎn)
newIndexToOldIndexMap[newIndex - s2] = i + 1 // (B)
所以處理完 c1 中的節(jié)點(diǎn)后，將有
moved = true
newIndexToOldIndexMap = [4, 5, 3, 0]
那么，increasingNewIndexSequence 的值就是 getSequence(newIndexToOldIndexMap)的返回值
// [4, 5, 3, 0] --> 最長(zhǎng)遞增子序列是 [4, 5]
// 對(duì)應(yīng)的索引是 [0, 1]
increasingNewIndexSequence = [0, 1]
在求解得到最長(zhǎng)遞增子序列之后，剩下的就是遍歷 c2 中的待處理節(jié)點(diǎn)，判斷是否節(jié)點(diǎn)是否屬于新增，是否需要進(jìn)行移動(dòng)。
j = increasingNewIndexSequence.length - 1
// looping backwards so that we can use last patched node as anchor
// 注意：這里是從后往前遍歷
for (i = toBePatched - 1; i >= 0; i--) {
const nextIndex = s2 + i
const nextChild = c2[nextIndex]
const anchor =
nextIndex + 1 < l2 ? (c2[nextIndex + 1]).el : parentAnchor
// newIndexToOldIndexMap 里的值默認(rèn)初始化為 0
// 這里 === 0 表示 c2 中的節(jié)點(diǎn)在 c1 中沒有對(duì)應(yīng)的節(jié)點(diǎn)，屬于新增
if (newIndexToOldIndexMap[i] === 0) {
// mount new
patch(
null,
nextChild,
container,
anchor,
parentComponent,
parentSuspense,
isSVG
)
} else if (moved) {
// move if:
// There is no stable subsequence (e.g. a reverse)
// OR current node is not among the stable sequence
// j < 0 --> 最長(zhǎng)遞增子序列為 []
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor, MoveType.REORDER)
} else {
j--
}
}
}
最長(zhǎng)遞增子序列
在計(jì)算機(jī)科學(xué)中，最長(zhǎng)遞增子序列（longest increasing subsequence）問題是指，在一個(gè)給定的數(shù)值序列中，找到一個(gè)子序列，使得這個(gè)子序列元素的數(shù)值依次遞增，并且這個(gè)子序列的長(zhǎng)度盡可能地大。最長(zhǎng)遞增子序列中的元素在原序列中不一定是連續(xù)的。-- 維基百科
對(duì)于以下的原始序列
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
最長(zhǎng)遞增子序列為
0, 2, 6, 9, 11, 15.
值得注意的是原始序列的最長(zhǎng)遞增子序列并不一定唯一，對(duì)于該原始序列，實(shí)際上還有以下兩個(gè)最長(zhǎng)遞增子序列
0, 4, 6, 9, 11, 15
0, 4, 6, 9, 13, 15
最后
至此，Vue 3.0 的 diff 代碼就分析完了，歡迎一起討論。
具體的代碼：https://github.com/vuejs/vue-next/blob/master/packages/runtime-core/src/renderer.ts
- EOF -