Vue源碼剖析（三）patch和Diff算法

2019-10-30    seo達(dá)人

Patch和Diff算法

網(wǎng)上看了好多的博客和源碼教程，感覺(jué)很多仔細(xì)的地方?jīng)]有說(shuō)清，而且在一些復(fù)雜的部分加了好多的描述，所以就想自己也寫(xiě)下心得, 方便自己, 方便他人，有興趣的同學(xué)可以關(guān)注我的github里面有我之前一些博文 github/193Eric



我們知道的，在數(shù)據(jù)更改后，會(huì)觸發(fā)getter，然后通過(guò)dep.notify()來(lái)通知watcher觸發(fā)update進(jìn)而更新視圖，最終是通過(guò)Diff算法來(lái)對(duì)比新老Vnode的差異，并把差異更新到Dom視圖上



Diff

我們知道的，Virtual DOM是一顆樹(shù)，而diff算法主要把兩顆樹(shù)進(jìn)行對(duì)比，找出之間的差異，來(lái)渲染頁(yè)面



diff 算法是通過(guò)同層的樹(shù)節(jié)點(diǎn)進(jìn)行比較而非對(duì)樹(shù)進(jìn)行逐層搜索遍歷的方式，所以時(shí)間復(fù)雜度只有 O(n)，是一種相當(dāng)?shù)乃惴?br />


1.調(diào)用patch函數(shù)比較Vnode和OldVnode,如果不一樣直接return Vnode即將Vnode真實(shí)化后替換掉DOM中的節(jié)點(diǎn)



2.如果OldVnode和Vnode值得進(jìn)一步比較則調(diào)用patchVnode方法進(jìn)行進(jìn)一步比較，分為以下幾種情況：



Vnode有子節(jié)點(diǎn)，但是OldVnode沒(méi)有，則將Vnode的子節(jié)點(diǎn)真實(shí)化后添加到真實(shí)DOM上



Vnode沒(méi)有子節(jié)點(diǎn)，但是OldVnode上有，則將真實(shí)DOM上相應(yīng)位置的節(jié)點(diǎn)刪除掉



Vnode和OldVnode都有文本節(jié)點(diǎn)但是內(nèi)容不一樣，則將真實(shí)DOM上的文本節(jié)點(diǎn)替換為Vnode上的文本節(jié)點(diǎn)



Vnode和OldVnode上都有子節(jié)點(diǎn)，需要調(diào)用updateChildren函數(shù)進(jìn)一步比較



updateChildren比較規(guī)則



提取出Vnode和OldVnode中的子節(jié)點(diǎn)分別為vCh和OldCh，并且提出各自的起始和結(jié)尾變量標(biāo)記為 oldS oldE newS newE



如果是oldS和newE匹配上了，那么真實(shí)dom中的第一個(gè)節(jié)點(diǎn)會(huì)移到最后



如果是oldE和newS匹配上了，那么真實(shí)dom中的最后一個(gè)節(jié)點(diǎn)會(huì)移到最前，匹配上的兩個(gè)指針向中間移動(dòng)



如果都沒(méi)有，在沒(méi)有key的情況下直接在DOM的oldS位置的前面添加newS，同時(shí)newS+1。在有key的情況下會(huì)將newS和Oldch上的所有節(jié)點(diǎn)對(duì)比，如果有相同的則移動(dòng)DOM并且將舊節(jié)點(diǎn)中這個(gè)位置置為null且newS+1。如果還沒(méi)有則直接在DOM的oldS位置的前面添加newS且newS+1

直到出現(xiàn)任意一方的start>end，則有一方遍歷結(jié)束，整個(gè)比較也結(jié)束



updateChildren例子：



假設(shè):



真實(shí)dom為 A、B、C

oldDom為 A1、B1、C1

newDom為 A2、D2、C2、B2



先確定oldS = A1 ; oldE = C1; newS = A2; newE = B2



先對(duì)比oldS和newS,oldE和newE,發(fā)現(xiàn)oldS = newS 所以真實(shí)dom的A固定不動(dòng)。排序?yàn)?A、B、C

然后oldS = B1 ; oldE = C1; newS = D2; newE = B2



對(duì)比發(fā)現(xiàn) oldS = newE , 所以真實(shí)dom,B要插入到后面去



真實(shí)dom排序?yàn)椋篈、C、B



然后oldS = C1; oldE = C1; newS = D2; newE = B2



對(duì)比發(fā)現(xiàn)兩兩都不對(duì)等，所以走第三步。

假設(shè)有key存在，所以newS直接和oldDom里面的所有節(jié)點(diǎn)對(duì)比，發(fā)現(xiàn)沒(méi)有存在，然后插入到oldS前面，且newS+1

真實(shí)dom排序?yàn)椋篈、D、C、B

然后重新開(kāi)始，oldS++ > oldE-- ,結(jié)束了。



這就是updateChildren，之后就是一直遍歷，運(yùn)行updateChildren直到?jīng)]有


日歷

鏈接

個(gè)人資料

存檔