Vue3 源碼分析 - 完整 update 流程和 diif 算法
前言
在上一篇文章 vue 的首次渲染過程中提到在組件的首次渲染階段會有一個副作用渲染函數setupRenderEffect，在這個函數內會使用響應式API Effect創建副作用函數componentEffect，這裏只需要簡單的理解爲，當組件內的數據改動時這個由Effect包裹的componentEffect就會重新調用，在這個函數內部會判斷當前組件是處於首次渲染還是更新，當組件內數據發生變化時會進入到update的分支，本文要看的diff流程也就是從這裏開始。
PS: 當前的
Vue版本是3.0.5。本文會忽略TELEPORT、SUSPENSE等特殊vnode類型，對於一些細微的優化也會忽略（比如patch函數的optimized參數）。
回顧 setupRenderEffect
在組件的數據發生改變時會自動觸發副作用渲染函數setupRenderEffect：
// runtime-core/src/renderer.ts
import { effect } from '@vue/reactivity'
const setupRenderEffect = (instance, initialVNode, container, ...) => {
// 在當前的組件實例上添加 update 方法，通過響應式方法 effect 創建
instance.update = effect(function componentEffect() {
if (!instance.isMounted) {
//...
} else {
// 非首次渲染，進入 update 階段
let { next, vnode } = instance
// 緩存一份更新後的 vnode
let originNext = next
if (next) {
// 這裏需要把更新後的組件 vnode 賦值 el，因爲下面第一次 渲染新的組件 vnode 時並沒有設置 el
next.el = vnode.el
updateComponentPreRender(instance, next)
} else {
// 如果沒有 next 直接指向當前 vnode
next = vnode
}
// 渲染新的組件 vnode，因爲數據發生了變化
const nextTree = renderComponentRoot(instance)
// 緩存舊的組件 vnode
const preTree = instance.subTree
// 更新實例上的 subTree 爲新的組件 vnode
instance.subTree = nextTree
patch(prevTree, nextTree, ..., instance)
// 更新 DOM 元素
next.el = nextTree.el
}
}, prodEffectOptions)這裏主要看update的部分（即else代碼塊）。首先會先從組件實例instance裏取出next（在處理組件一節會詳細說明next存在與不存在的情況）。
組件內的數據發生了改變，所以要生成新的組件模板的vnode節點，在渲染階段命名爲subTree，然後還要保存一份舊的subTree，這樣有了新舊subTree後就可以用patch函數更新DOM。
patch 函數
在進入具體的diff流程之前，我們不妨先想一下，當數據發生改變時，會有哪些變化類型？
實際上按照類型可以分爲更新普通DOM元素和更新vue組件這兩種情況。下面先關注一下patch函數的邏輯。
// runtime-core/src/renderer.ts
const patch = (n1, n2, container, ...) => {
// n1 是舊節點，n2 是新節點
// 如果 n1、n2 新舊節點的類型不同，直接銷燬舊節點
if(n1 && !isSameVNodeType(n1, n2)) {
unmount(n1, parentComponent, parentSuspense, true)
n1 = null
}
const { type, ref, shapeFlag } = n2
switch(type) {
// 處理文本節點
case Text:
processText(n1, n2, container, anchor)
break
// 處理註釋
case Comment:
processCommentNode(n1, n2, container, anchor)
break
// ...
default:
// 處理 DOM 元素
if(shapeFlag & ShapeFlags.ELEMENT) {
processElement(n1, n2, container, ...)
// 處理 vue 組件
} else if (shapeFlag & ShapeFlags.COMPONENT) {
processComponent(n1, n2, container, ...)
}
// ...
}
}最開始先判斷新舊節點的類型是否一樣，如果不一樣，可以設想某個節點從div標籤變成span標籤，最合理的方式是直接捨棄舊節點，重新掛載新的節點。
再往下會根據當前節點類型type進行特定的處理。比如文本節點執行processText的特定處理、註釋節點執行processCommentNode的特定處理。這樣的前置處理實際上是一個優化，在編譯階段，vue會將模版語法編譯成渲染函數，這個時候會把第一個參數節點類型type填上，如果這個參數命中了這樣的特殊節點，會直接執行相應的process方法。
default塊兒裏纔是分析的重點，即處理普通DOM元素和vue組件。
處理 DOM 元素
先舉一個栗子🌰，假設有以下一段代碼：
<template>
<div>
<button @click="add">add</button>
<p>{{ num }}</p>
</div>
</template>
<script>
import { ref } from 'vue'
export default {
setup () {
const num = ref(1)
function add() {
num.value += 1
}
return {
num,
add
}
}
}
</script>這段代碼非常簡單，點擊add按鈕，p標籤裏的num會加一。
因爲p標籤是一個普通的DOM節點，所以在具體執行patch方法時，會走處理DOM的邏輯，執行processElement方法。
// runtime-core/src/renderer.ts
const processElement= (n1, n2, container, ...) => {
// 無舊節點，首次渲染邏輯
if (n1 === null) {
// ...
} else {
patchElement(n1, n2, ...)
}
}我們只關心新舊節點都存在的update邏輯，所以接着看patchElement函數。
前置屬性
在具體看patchElement之前，我們需要先了解兩個前置屬性：
1. PatchFlags
在vnode中有patchFlag這樣一個字段，用來表示當前節點發生改變的類型。PatchFlags的所有枚舉類型如下所示：
// shared/src/patchFlags.ts
export const enum PatchFlags {
TEXT = 1,
CLASS = 1 << 1,
STYLE = 1 << 2,
PROPS = 1 << 3,
FULL_PROPS = 1 << 4,
HYDRATE_EVENTS = 1 << 5,
STABLE_FRAGMENT = 1 << 6,
KEYED_FRAGMENT = 1 << 7,
UNKEYED_FRAGMENT = 1 << 8,
NEED_PATCH = 1 << 9,
DYNAMIC_SLOTS = 1 << 10,
DEV_ROOT_FRAGMENT = 1 << 11,
HOISTED = -1,
BAIL = -2
}patchFlag所有的枚舉類型都由二進制來表示，這樣做的好處是很容易對多種類型進行判斷，比如當前變化包括TEXT和CLASS。
在判斷時，只需要對想要判斷的類型進行&操作，如果大於 0，說明包含此類型。
TEXT & CLASS
2. dynamicChildren
vue3中對靜態節點做了標記，在patch階段，不會比較靜態節點，只會比較動態節點，即dynamicChildren內的節點。
patchElement
瞭解完上面兩個屬性後我們迴歸主線，看一下patchElement函數：
// runtime-core/src/renderer.ts
const patchElement = (n1, n2, ...) => {
// 緩存舊的DOM節點，因爲這是DOM的更新，所以舊DOM節點即 n1.el 一定存在
const el = (n2.el = n1.el!)
// 取出新節點的 patchFlag dynamicChildren 後面會進行判斷
let { patchFlag, dynamicChildren } = n2
// 保存舊節點 props
const oldProps = n1.props || {}
// 保存新節點 props
const newProps = n2.props || {}
if (patchFlag > 0) {
// 對所 props 都進行比較更新
if (patchFlag & PatchFlags.FULL_PROPS) {
patchProps(el, n2, oldProps, newProps, ...)
} else {
// 存在動態 class 屬性時
if (patchFlag & PatchFlags.CLASS) {
if (oldProps.class !== newProps.class) {
hostPatchProp(el, 'class', null, newProps.class, ...)
}
}
// 存在動態 style 屬性時
if (patchFlag & PatchFlags.STYLE) {
hostPatchProp(el, 'style', oldProps.style, newProps.style, ...)
}
// 針對除了 style、class 的 props
if (patchFlag & PatchFlags.PROPS) {
const propsToUpdate = n2.dynamicProps!
for (let i = 0; i < propsToUpdate.length; i++) {
const key = propsToUpdate[i]
const prev = oldProps[key]
const next = newProps[key]
if (next !== prev) {
hostPatchProp(el, key, prev, next, ...)
}
}
}
// 存在動態 文本
if (patchFlag & PatchFlags.TEXT) {
if (n1.children !== n2.children) {
hostSetElementText(el, n2.children as string)
}
}
} else if (dynamicChildren == null) {
patchProps(el, n2, oldProps, newProps, ...)
}
}
if (dynamicChildren) {
patchBlockChildren(n1.dynamicChildren!, dynamicChildren, el, ...)
} else {
patchChildren(n1, n2, el, null, ...)
}
}對於DOM節點的更新主要是props和子節點的更新，其中利用patchFlag和dynamicChildren做了很多優化，不會每次都對 props 和子節點進行全量的對比更新。
下面這兩張圖對代碼裏的一些if else分支做了總結，vue3會充分利用patchFlag和dynamicChildren做優化，如果確定只是某個局部的變動，比如STYLE改變，那麼只會調用hostPatchProp並傳入對應的參數STYLE做特定的更新。
更新子節點
下面一一看下上圖提到的幾個函數具體做了什麼：
hostPatchProp``hostPatchProp函數會根據參數的key執行相應的方法，比較簡單。
// runtime-dom/src/patchProp.ts
export const patchProp = (el, key, prevValue, nextValue, ...) => {
switch (key) {
case 'class':
// 更新 class
patchClass(el, nextValue, isSVG)
break
case 'style':
// 更新 style
patchStyle(el, prevValue, nextValue)
break
default:
// ...
patchAttr(el, key, nextValue, isSVG)
}
}這幾個方法都比較類似，最終都是調用原生的DOM API更新，其中看下patchClass方法，這個方法比較有意思的一點是，源碼中註釋寫直接對className賦值比使用setAttribute方法要快，不得不說真的細 hhhh。
// runtime-dom/src/modules/class.ts
export function patchClass(el, value) {
if (value == null) {
value = ''
}
...
// directly setting className should be faster than setAttribute in theory
el.className = value
}patchProps``patchProps就如其名了，遍歷所有屬性，全部進行更新。
// runtime-core/src/renderer.ts
const patchProps = (el, vnode, oldProps, newProps, ...) => {
if (oldProps !== newProps) {
// 遍歷 newProps 更新
for (const key in newProps) {
const next = newProps[key]
const prev = oldProps[key]
if (next !== prev) {
hostPatchProp(el, key, prev, next, ...)
}
}
if (oldProps !== EMPTY_OBJ) {
// 遍歷 oldProps
for (const key in oldProps) {
// 如果 存在某個屬性 不在 newProps 調用 hostPatchProp 移除該屬性
if (!(key in newProps)) {
hostPatchProp(el, key, oldProps[key], null,...)
}
}
}
}
}patchBlockChildren
DOM是一顆樹，不難想到會有子節點嵌套的情況，所以這裏的子節點更新是一個深度優先遍歷的過程，即更新完當前節點後，會去更新當前節點的子節點，不過vue3在這個過程中有所優化。具體會通過對patch的最後一個參數optimized傳參來防止不必要的渲染。這裏簡單知道有這個優化即可，全部羅列出來比較繁瑣，感興趣的同學可以詳細看看。
這個方法也比較簡單，因爲在編譯的時候已經確定了哪些是動態節點，所以直接遍歷所有的動態節點然後進行patch即可。
// runtime-core/src/renderer.ts
const patchBlockChildren = (oldChildren, newChildren, fallbackContainer, ...) => {
for (let i = 0; i < newChildren.length; i++) {
const oldVNode = oldChildren[i]
const newVNode = newChildren[i]
patch(oldVNode, newVNode, container, ...)
}
}patchChildren
對於子節點來說，只會有三種可能，分別是：文本節點、數組和空。所以這個方法裏所有的if else分支就是在考慮新舊節點可能的全部情況，並進行相應的處理。
// runtime-core/src/renderer.ts
const patchChildren = (n1, n2, container, ...) => {
const c1 = n1 && n1.children
const prevShapeFlag = n1 ? n1.shapeFlag : 0
const c2 = n2.children
const { patchFlag, shapeFlag } = n2
// ...
// children has 3 possibilities: text, array or no children.
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
// text children fast path
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 如果舊子節點是數組 先卸載
unmountChildren(c1, parentComponent, parentSuspense)
}
if (c2 !== c1) {
// 更新文本節點
hostSetElementText(container, c2)
}
} else {
if (prevShapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// 舊子節點是數組
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
// two arrays, cannot assume anything, do full diff
patchKeyedChildren(c1, c2, container, ...)
} else {
// 沒有新子節點，直接卸載舊子節點
unmountChildren(c1, parentComponent, parentSuspense, true)
}
} else {
// prev children was text OR null
// new children is array OR null
if (prevShapeFlag & ShapeFlags.TEXT_CHILDREN) {
hostSetElementText(container, '')
}
// mount new if array
if (shapeFlag & ShapeFlags.ARRAY_CHILDREN) {
mountChildren(c2, container, ...)
}
}
}
}新舊節點情況
其中新舊節點都是數組的情況涉及到我們平常所說的diff算法，會放到後面專門去解析。
處理 vue 組件
看完處理DOM元素的情況，接下來看處理vue組件。再舉一個例子🌰：
<template>
<div>
<button @click="add">add</button>
<foo :num="num" />
</div>
</template>
<script>
import { ref } from 'vue'
export default {
setup () {
const num = ref(1)
function add() {
num.value += 1
}
return {
num,
add
}
}
}
</script>
// foo 組件
<template>
<div>
<p>num is, {{ num }}</p>
</div>
</template>
<script>
export default {
props: {
num: Number
}
}
</script>這個例子就是將之前的普通元素標籤換成了foo組件，foo組件接收num props，點擊add按鈕就會加一。
讓我們回到patch方法，當點擊add按鈕時會觸發重新渲染，其中更新foo時會進入processComponent方法。
// runtime-core/src/renderer.ts
const processComponent = (n1, n2, container, ...) => {
if (n1 === null) {
// 首次渲染
// ...
} else {
// 更新
updateComponent(n1, n2, ...)
}
}在更新的時候我們只關心updateComponent。
// runtime-core/src/renderer.ts
const updateComponent = (n1, n2, ...) => {
// 緩存最新的 組件 vnode
const instance = (n2.component = n1.component)!
// 對比新舊 vnode 節點，
if (shouldUpdateComponent(n1, n2)) {
// ...
// 把最新組件vnode 賦值給 instance.next
instance.next = n2
// in case the child component is also queued, remove it to avoid
// double updating the same child component in the same flush.
invalidateJob(instance.update)
// instance.update is the reactive effect runner.
instance.update()
} else {
// no update needed. just copy over properties
n2.component = n1.component
n2.el = n1.el
instance.vnode = n2
}
}在updateComponent方法內部，先緩存最新的組件實例，接下來有一個優化點，會通過shouldUpdateComponent方法來比較新舊組件是否需要更新，這裏主要是對比組件vnode的props、children等屬性。這樣的提前判斷會避免不必要的渲染，如果需要渲染，會把最新的組件vnode賦值給instance.next，這在下面調用組件首次渲染時註冊的instance.update副作用渲染函數時會使用到。
至於invalidateJob這個方法，它是從scheduler.ts文件中引出的，所以大概可以知道是處理調度相關。再結合註釋和傳入的參數，就比較明白了。DOM結構是一棵樹，從上面的流程中可以知道，在更新一個節點時不光會更新節點本身，還會更新節點的子節點，所以，vue會在這裏進行檢查，看是否當前組件的副作用函數已經在隊列中了，如果在，直接移除掉，反正再往下也會主動觸發更新。這樣就避免了二次重複渲染。
如果對比了新舊節點發現不需要更新，那很好辦，就不會主動調用instance.update觸發更新，僅僅是更新相關的屬性。
接着執行instance.update，這個函數就是在setupRenderEffect內創建的。最終子組件的更新還會走一遍自己副作用渲染函數，然後patch子組件的子模板DOM，接上上面的流程。
update 流程小結
其實到這裏可能還是不太清楚整個流程是怎樣的，還是以上面的例子爲代表，我們從頭捋一遍點擊add後到底經歷了哪些流程。首先我們有一個根組件app，app模板的根DOM元素是div，div裏面有button元素和foo組件。app與foo之間通過props: num通信，點擊button時num會加一。
當點擊add後，app組件內的num更新，由於初次渲染時在組件實例上添加了響應式的update方法。app組件會觸發自身的update。
// runtime-core/src/renderer.ts
// setupRenderEffect 函數內
instance.update = effect(function componentEffect() {
if (!instance.isMounted) {
...
} else {
let { next } = instance
if (next) {
updateComponentPreRender(instance, next)
} else {
next = vnode
}
const nextTree = renderComponentRoot(instance)
const prevTree = instance.subTree
instance.subTree = nextTree
patch(prevTree, nextTree, ..., instance)
}
}, prodEffectOptions)注意現在是app組件自身的數據變化，所以此時是沒有next的，接下來渲染新的子組件vnode，得到真實的模版vnode nextTree，用新舊subTree進行patch。
因爲對比的是app內模板的普通元素vnode，此時patch的元素類型是div，進入更新普通元素的流程，先更新props，再更新子節點，當前div下的子節點有button和foo組件，先更新button元素，再更新foo組件。
在更新foo組件時，會先將foo組件instance.next賦值爲最新的foo子組件vnode，之後再主動調用foo.update進入上面的副作用渲染函數，這次的實例是foo組件且next存在值。之後就是同樣的邏輯，進入foo組件的patch，後面就省略掉不細說了。
可以發現，一個組件的更新存在兩種情況。在副作用渲染函數的內部，如果next不存在，是組件本身數據發生變化引發的update，next存在，是父組件更新子組件的時候引發的update。
update 邏輯
diff 算法
在前面分析更新普通元素子節點時，有一種情況是新舊子節點都是數組，這個時候就需要某種成本較低的策略進行diff更新。
先假設所有元素都擁有一個獨一無二的
key值。
我們可以先想一下，新舊子節點都是數組會有哪幾種變化情況？
四種原子操作
無論是哪種變化最後都是由更新、添加、刪除、移動這四種操作的一種或者幾種的組合。
源碼裏面劃分的比較清晰，主要分爲了三種情況：在同一位置添加一個或多個節點、在同一位置刪除一個或多個節點和處理未知序列。
新舊數組序列情況
從上面這三種情況可以看出一個共性，從頭開始的一部分和從尾部倒序的一部分（所有淡黃色的）可能是不需要改變的，不論哪種情況整體都可以分爲從頭部正序不需要改動的部分、中間發生變動的部分、從尾部倒序不需要改動的部分。所以在最開始，可以先進行頭部和尾部的預處理。
源碼裏在diff算法的最開始，會先從頭部正序掃描和從尾部倒序掃描，以便排除類型一樣的干擾項，進一步的提高效率。
此處的類型一樣指
vnode節點的type、key都一樣。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// 從頭部開始掃描的索引
let i = 0
// 新節點長度
const l2 = c2.length
// 舊數組序列尾部索引
let e1 = c1.length - 1
// 新數組序列尾部索引
let e2 = l2 - 1
// 1. 正序掃描頭部，找到不相同的爲止
while (i <= e1 && i <= e2) {
// 當前掃描到的舊數組序列中的節點
const n1 = c1[i]
// 當前掃描到的新數組序列中的節點
const n2 = c2[i]
// 如果當前的新舊節點 type、key 相同，才爲 true
if (isSameVNodeType(n1, n2)) {
// 更新
patch(n1, n2, ...)
} else {
break
}
i++
}
// 2. 倒序掃描尾部，找到不相同的爲止
while (i <= e1 && i<= e2) {
// 當前掃描到的舊數組序列中的節點
const n1 = c1[e1]
// 當前掃描到的新數組序列中的節點
const n2 = c2[e2]
if (isSameVNodeType(n1, n2)) {
patch(n1, n2, ...)
} else {
break
}
e1--
e2--
}
// ...
}這段代碼就像上面說到的那樣，先從頭部正序掃描，再從尾部倒序掃描，終止的條件是當前索引不能越界或者遇到新舊數組序列中的節點，類型不一樣或者key值不一樣，掃描到相同的節點會進行patch更新，這裏不用操心當前的節點到底是否需要更新，patch函數內部會做相關的判斷。
同一位置的添加、刪除
這種情況相對而言比較簡單，因爲只涉及到添加或者刪除這兩種單一的原子操作之一，且位置還都是固定。
只需要掃描頭部尾部，找出是在哪個位置進行的添加或刪除，之後再進行相應的操作即可。
添加節點使用這個例子，從頭部和從尾部掃描完畢之後，各個變量情況如圖所示。
同一位置添加節點
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的爲止
// 2. 倒序掃描尾部，找到不相同的爲止
// 3. if (同一位置添加節點)
if (i > e1) {
if (i <= e2) {
const nextPos = e2 + 1
const anchor = nextPos < l2 ? (c2[nextPos].el : parentAnchor
while (i <= e2) {
// 第一個參數 舊節點 爲 null，新的掛載節點
patch(null, c2[i], ...)
i++
}
}
}
// ...
}如果i > e1 && i <= e2，第一個條件語句表示當前索引已經到了舊數組序列除去尾部相同節點的末尾，但是還沒到新數組序列除去尾部相同節點的末尾，意味着新的數組序列在舊的數組序列上新添加了一個或多個的連續節點，所以自然而然會命中新添加節點的情況。只需要對[i, e2]這個新數組序列內的節點依次進行掛載即可。
當然，如果掃描完畢後情況相反，即當前索引到了新數組序列除去尾部相同節點的末尾，但是還沒到舊數組序列除去尾部相同節點的末尾，即發生變化的索引區間新數組序列小於舊數組序列的，這意味着新數組序列在舊數組序列的基礎上刪除了一個或多個節點。只需要對[i, e2]這個舊數組序列內的節點依次進行卸載即可。
同一位置刪除節點
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的爲止
// 2. 倒序掃描尾部，找到不相同的爲止
// 3. if (同一位置添加節點) 沒有命中
// 4. else if (同一位置刪除節點)
else if (i > e2) {
if (i <= e1) {
while (i <= e1) {
unmount(c1[i], ...)
i++
}
}
}
// ...
}未知數組序列
如果沒有命中上面的兩種情況，那麼就需要處理未知數組序列了。看一下下面這個例子。
中間變化區域是未知序列
先人工分析一下，中間發生變動的部分經過了哪些改變：
-
有節點的移動，
d節點移動到c節點前，e節點移動到d節點前。 -
有節點的添加，添加了
h節點。
按照之前的流程，仍舊是先進行頭部與尾部的預處理掃描，通過i、e1、e2圈出發生改動的區間。這個例子不符合添加和刪除的分支，所以進入最後一個elsec 處理未知序列的代碼塊 。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的爲止
// 2. 倒序掃描尾部，找到不相同的爲止
// 3. if (同一位置添加節點) 沒有命中
// 4. else if (同一位置刪除節點) 沒有命中
// 5. else 處理未知數組序列
else {
// 舊數組未知序列開始索引
const s1 = i
// 新數組未知序列開始索引
const s2 = i
// 5.1 創建新數組未知序列的 key -> 索引 map
const keyToNewIndexMap = new Map()
// 因爲針對新數組未知序列創建 map，所以臨界是 e2
for (i = s2; i <= e2; i++) {
// 遍歷到的新數組的節點
const nextChild = c2[i]
// 前面已經假設一定存在 key 值
if (nextChild.key !== null) {
// 存儲的 <key, value> 是 節點 key 值、索引
keyToNewIndexMap.set(nextChild.key, i)
}
}
// ...
}
// ...
}註釋5開始現在正式進入到處理未知序列的流程中，會根據新數組的未知序列建立一個keyToNewIndexMap<key, index>的map結構。只需要遍歷新數組的未知序列即可，得到{ e: 2, d: 3, c: 4, h: 5 }。
建立 keyToNewIndexMap
遍歷舊數組序列進行選擇性的更新和移除
下面我們遍歷舊數組的未知序列，根據key值且對照着剛剛建立的keyToNewIndexMap，查找舊數組序列中哪些節點仍然存在可以patch、哪些節點不存在需要移除、哪些節點需要移動。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的爲止
// 2. 倒序掃描尾部，找到不相同的爲止
// 3. if (同一位置添加節點) 沒有命中
// 4. else if (同一位置刪除節點) 沒有命中
// 5. else 處理未知數組序列
else {
// 舊數組未知序列開始索引
const s1 = i
// 新數組未知序列開始索引
const s2 = i
// 5.1 創建新數組未知序列的 key -> 索引 map
// 5.2 遍歷舊數組未知序列，使用 key 值，根據keyToNewIndexMap 找出哪些節點需要patch、移除、移動
// 新舊數組中已經 patch 過的節點數
let patched = 0
// 所有待處理的節點，是新數組未知序列的長度
const toBePatched = e2 - s2 + 1
// 是否有節點需要移動
let moved = false
// used to track whether any node has moved 跟蹤是否有節點移動
let maxNewIndexSoFar = 0
// 這個數組本身的 index 代表新數組元素的索引，數組的值代表舊數組元素的索引
const newIndexToOldIndexMap = new Array(toBePatched)
// 初始化數組值爲 0
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0
// 遍歷舊數組未知序列
for (i = s1; i <= e1; i++) {
// 當前的 舊節點
const prevChild = c1[i]
// 如果已經 patch 過的舊節點數大於等於 所有新數組中待處理的節點
// 說明所有新數組中的節點都已經 patch 完畢，其餘的要移除
if (patched >= toBePatched) {
unmount(prevChild, ...)
continue
}
let newIndex
// 假設 key 一定存在
if (prevChild.key != null) {
// 從 keyToNewIndexMap 中獲取當前節點在新數組中的索引
newIndex = keyToNewIndexMap.get(prevChild.key)
}
// 如果當前節點在新數組中找不到，說明新數組中沒有，移除該節點
if (newIndex === undefined) {
unmount(prevChild, ...)
} else {
// 更新數組，因爲默認值是 0，i 有可能是 0，+ 1 避免和默認值衝突
newIndexToOldIndexMap[newIndex - s2] = i + 1
// maxNewIndexSoFar 初始值是0
// 每次maxNewIndexSoFar賦值的是當前節點在 新數組中的索引
// 如果新數組的順序和舊數組一樣，那麼就是遞增的
// false 說明順序發生改變
if (newIndex >= maxNewIndexSoFar) {
maxNewIndexSoFar = newIndex
} else {
moved = true
}
// patch 新舊節點中匹配的節點
patch(prevChild. c2[newIndex], ...)
// 當前 patch 過的節點數 +1
pached++
}
}
}
// ...
}因爲現在的DOM還是由舊數組生成的，我們需要知道當前的這些舊DOM節點是需要更新還是刪除還是移動。所以我們要去遍歷舊數組的未知序列，並結合剛生成的keyToNewIndexMap與新數組的未知序列進行對比。
先定義了幾個變量。patched表示當前已經更新的節點數，toBePatched表示當前待更新的全部節點，通過這個描述我們也就知道了，如果patched大於等於toBePatched，那麼剩下的舊節點就是要全部捨棄的。
moved用來表示當前是否有移動的節點。
maxNewIndexSoFar用來判斷是否有節點移動。
newIndexToOldIndexMap這個數組本身的index代表當前節點在新數組序列中的索引，實際的值代表當前節點舊子序列索引。默認值全部是 0。
接下來開始正式遍歷舊數組，先取出舊數組序列裏的節點c1[i]，然後判斷patched是否大於等於toBePatched，如果是，卸載當前的舊節點，跳出本次循環。
如果當前更新的節點數沒有大於等於所有待更新的節點數，那麼開始更新keyToNewIndexMap這個數組，只需要通過key值從newIndexToOldIndexMap內取出相應的newIndex索引即可。
如果找不到索引，說明在新的數組序列中這個節點不存在，直接刪除此節點。
如果找到了這個索引，那麼更新newIndexToOldIndexMap[newIndex - s2] = i + 1，這裏爲什麼要i+1呢？因爲這個數組的默認值設置爲了0，如果當前的i就是0，會引起衝突。
再往下執行，因爲maxNewIndexSoFar 初始值是0，每次maxNewIndexSoFar賦值的是當前節點在新數組中的索引，如果新數組的順序和舊數組一樣，那麼每次的maxNewIndexSoFar不可能大於newIndex。如果大於了，說明有節點發生了移動，需要將moved設置爲true。
最後，沒有經過前面的刪除，證明當前的這個節點在新舊節點中都是存在的，那麼直接patch(prevChild, c2[newIndex])即可。最後別忘記把記錄已更新節點數變量patched加一。
遍歷舊數組後結果
移動和掛載新節點
通過moved變量，我們已經知道了當前有節點移動，下面需要處理的就是移動和掛載新節點。
vue3移動節點採取的策略是先得到最長遞增子序列的索引newIndexToOldIndexMap。舉個列子：
[2, 3, 1, 0]的最長遞增子序列是[2, 3]，最終需要的索引是[0, 1]
關於如何求解最長遞增子序列，推薦看 leetcode300 最長遞增子序列題解，在這裏就不贅述具體算法實現了，主要目標仍然是在整體流程。
// runtime-core/src/renderer.ts
const patchKeyedChildren = (c1, c2, ...) => {
// ...
// 1. 正序掃描頭部，找到不相同的爲止
// 2. 倒序掃描尾部，找到不相同的爲止
// 3. if (同一位置添加節點) 沒有命中
// 4. else if (同一位置刪除節點) 沒有命中
// 5. else 處理未知數組序列
else {
// 5.1 創建新數組未知序列的 key -> 索引 map
// 5.2 遍歷舊數組未知序列，使用 key 值，根據keyToNewIndexMap 找出哪些節點需要patch、移除、移動
// 5.3 移動和掛載新節點
// 如果有節點移動，得到 newIndexToOldIndexMap 的最長遞增子序列的索引
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR
// 用於節點移動判斷
let j = increasingNewIndexSequence.length - 1
// 倒序新數組的未知序列，因爲插入節點時使用 insertBefore 即向前插，倒序遍歷可以使用上一個更新的節點作爲錨點
for (i = toBePatched - 1; i >= 0; i--) {
// 當前在整個新數組中，未知序列的索引，s2 是頭部相同節點的偏移量
const nextIndex = s2 + i
// 當前在整個新數組中，未知序列的節點
const nextChild = c2[nextIndex]
// 當前節點的下一個節點，如果當前節點是最後一個節點，那麼取整個父節點的下一個節點作爲插入點
const anchor = nextIndex + 1 < l2 ? c2[nextIndex + 1] : parentAnchor
// 如果仍然是默認值 0 證明是一個全新的節點
if (newIndexToOldIndexMap[i] === 0) {
// 掛載新的節點
patch(null, nextChild, container, anchor, ...)
// 存在節點移動
} else if (moved) {
// 當前索引不是最長遞增子序列裏的值，需要移動
if (j < 0 || i !== increasingNewIndexSequence[j]) {
move(nextChild, container, anchor)
// 當前索引是最長遞增子序列裏的值，j 指向下一個
} else {
j--
}
}
}
}
// ...
}在得到最長遞增子序列索引後，設置一個變量j，它的初始值是最長遞增子序列索引的length - 1，即指向其末尾，主要是用來判斷節點是否需要移動。
下面會倒序遍歷新數組的未知序列，因爲無論是在patch中還是下面移動節點的move方法，其插入節點的操作都是使用insertBefore向前插入。在每一次倒序遍歷的時候，如果需要的話我們可以很輕鬆的選取上一次已經處理完畢的節點作爲基準，把當前節點，插入到它的前面。
進入到每一輪的遍歷，其實會出現三種情況：
-
使用
newIndexToOldIndexMap用當前的新數組索引查找舊數組索引，發現是初始值0，表示舊數組中沒有這個節點，那麼使用patch方法掛載一個新的節點即可。 -
當前的索引不在最長遞增子序列中（
j < 0會越界，所以提前可以確定不存在），說明當前節點需要移動，那麼調用move(nextChild, container, anchor)即可。 -
當前的索引恰好是最長遞增子序列的值，說明該節點不需要移動，維護
j變量。
到這兒，完成了對於未知序列的更新就完成了，下面看一下當前這個例子的具體執行過程。
具體執行過程
沒有 key 值的情況
上面的流程一直在假設每一個節點都有一個獨一無二的key值，如果我們不寫key值會怎樣呢？
因爲一般數組渲染都會使用
v-for，所以在這裏這個沒有 key 值的情況指所有的新舊數組節點都沒有key，而非有的節點存在key，有的節點不存在key。
如果沒有寫key值，在patchChildren函數內，會根據patchFlag進入patchUnkeyedChildren這個函數內。
// runtime-core/src/renderer.ts
const patchChildren = (n1, n2, ...) => {
// ...
if (patchFlag & PatchFlags.KEYED_FRAGMENT) {
patchKeyedChildren(...)
return
} else if (patchFlag & PatchFlags.UNKEYED_FRAGMENT) {
// 無 key 值的情況
patchUnkeyedChildren(...)
return
}
// ...
}其實對於不寫key值的diff處理非常的簡單粗暴，會先取新舊數組長度較小的作爲公共長度，然後以這個較小的長度挨個進行遍歷並對新舊數組的節點patch。
之後判斷：
-
如果新數組的長度大於舊數組，說明有新增的節點，那麼只需要接着掛載即可。
-
如果新數組的長度小於舊數組，說明有刪除的節點，那麼只需要從尾部開始刪除即可。
// runtime-core/src/renderer.ts
const patchUnkeyedChildren = (c1, c2, ...) => {
c1 = c1 || EMPTY_ARR
c2 = c2 || EMPTY_ARR
const oldLength = c1.length
const newLength = c2.length
// 選取較小長度作爲公共部分
const commonLength = Math.min(oldLength, newLength)
// 依次 patch
for (let i = 0; i < commonLength; i++) {
const nextChild = c2[i]
patch(c1[i], nextChild, ...)
}
if (oldLength > newLength) {
// remove old
unmountChildren(...)
} else {
// mount new
mountChildren(...)
}
}舉個例子🌰：
沒有 key 值 diff
我們可以很明顯的看出這種情況的不足：沒有利用任何一箇舊節點，全部進行無腦的patch更新。
最後
到此，你已經看完了vue3更新時的整個流程和完整的diff算法～如果有收穫的話，點個贊支持一下吧～
參考資料
-
https://github.com/vuejs/vue-next/blob/master/packages/runtime-core/src/renderer.ts
-
https://juejin.cn/post/6919376064833667080
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/GGNYhTgPWj0wR3ReoX_Sng