diff源碼

㈠ 面試中的網紅Vue源碼解析之虛擬DOM，你知多少呢深入解讀diff演算法

眾所周知，在前端的面試中，面試官非常愛考dom和diff演算法。比如，可能會出現在以下場景

滴滴滴，面試官發來一個面試邀請。接受邀請📞

我們都知道， key 的作用在前端的面試是一道很普遍的題目，但是呢，很多時候我們都只浮於知識的表面，而沒有去深挖其原理所在，這個時候我們的競爭力就在這被拉下了。所以呢，深入學習原理對於提升自身的核心競爭力是一個必不可少的過程。

在接下來的這篇文章中，我們將講解面試中很愛考的虛擬DOM以及其背後的diff演算法。 請認真閱讀本文～文末有學習資源免費共享！！！

虛擬DOM是用JavaScript對象描述DOM的層次結構。DOM中的一切屬性都在虛擬DOM中有對應的屬性。本質上是JS 和 DOM 之間的一個映射緩存。

要點：虛擬 DOM 是 JS 對象；虛擬 DOM 是對真實 DOM 的描述。

diff發生在虛擬DOM上。diff演算法是在新虛擬DOM和老虛擬DOM進行diff（精細化比對），實現最小量更新，最後反映到真正的DOM上。

我們前面知道diff演算法發生在虛擬DOM上，而虛擬DOM是如何實現的呢？實際上虛擬DOM是有一個個虛擬節點組成。

h函數用來產生虛擬節點（vnode）。虛擬節點有如下的屬性：
1）sel： 標簽類型，例如 p、div；
2）data： 標簽上的數據，例如 style、class、data-*；
3）children ：子節點；
4） text： 文本內容；
5）elm：虛擬節點綁定的真實 DOM 節點；

通過h函數的嵌套，從而得到虛擬DOM樹。

我們編寫了一個低配版的h函數，必須傳入3個參數，重載較弱。

形態1：h('div', {}, '文字')
形態2：h('div', {}, [])
形態3：h('div', {}, h())

首先定義vnode節點，實際上就是把傳入的參數合成對象返回。

[圖片上傳失敗...(image-7a9966-1624019394657)]
然後編寫h函數，根據第三個參數的不同進行不同的響應。

當我們進行比較的過程中，我們採用的4種命中查找策略：
1）新前與舊前：命中則指針同時往後移動。
2）新後與舊後：命中則指針同時往前移動。
3）新後與舊前：命中則涉及節點移動，那麼新後指向的節點，移到 舊後之後 。
4）新前與舊後：命中則涉及節點移動，那麼新前指向的節點，移到 舊前之前 。

命中上述4種一種就不在命中判斷了，如果沒有命中，就需要循環來尋找，移動到舊前之前。直到while(新前<=新後&&舊前<=就後)不成立則完成。

如果是新節點先循環完畢，如果老節點中還有剩餘節點(舊前和舊後指針中間的節點)，說明他們是要被刪除的節點。

如果是舊節點先循環完畢，說明新節點中有要插入的節點。

1.什麼是Virtual DOM 和Snabbdom
2.手寫底層源碼h函數
3.感受Vue核心演算法之diff演算法
4.snabbdom之核心h函數的工作原理

1、零基礎入門或者有一定基礎的同學、大中院校學生
2、在職從事相關工作1-2年以及打算轉行前端的朋友
3、對前端開發有興趣人群

㈡ Linux里 .diff 是什麼文件在gnu下了個gcc源碼包，看到有個.diff文件，這是什麼文件

就是 difference 的意思。
這個東西是 diff 命令生成的「區別」數據，也就是兩個源代碼目錄他會識別出有什麼不同點並且輸出為 diff 文件特有的格式。這個輸出的文件可以用 patch 命令打在舊版本的源代碼上來實現變成新版本的源代碼。
這種升級源代碼版本的辦法，可以很好的解決每次下載源代碼都要重頭全部下載導致數據量很大的問題。

如果你下載源代碼包只有 .diff ，那麼證明你下載錯了，因為只有舊的特定版本才能用 diff 升級為特定的新版本。diff 文件是前後兩個版本關聯的，不是隨便可以用的。

㈢ web前端diff 演算法深入一下

有同學問：能否詳細說一下 diff 演算法。

詳細的說，請閱讀這篇文章，有疑問的地方歡迎留言一起討論。

因為 diff 演算法是 vue2.x ， vue3.x 以及 react 中關鍵核心點，理解 diff 演算法，更有助於理解各個框架本質。

說到「diff 演算法」，不得不說「虛擬 Dom」，因為這兩個息息相關。

比如：

等等

我們先來說說虛擬 Dom，就是通過 JS 模擬實現 DOM ，接下來難點就是如何判斷舊對象和新對象之間的差異。

Dom 是多叉樹結構，如果需要完整的對比兩棵樹的差異，那麼演算法的時間復雜度 O(n ^ 3)，這個復雜度很難讓人接收，尤其在 n 很大的情況下，於是 React 團隊優化了演算法，實現了 O(n) 的復雜度來對比差異。

實現 O(n) 復雜度的關鍵就是只對比同層的節點，而不是跨層對比，這也是考慮到在實際業務中很少會去跨層的移動 DOM 元素。

虛擬 DOM 差異演算法的步驟分為 2 步：

實際 diff 演算法比較中，節點比較主要有 5 種規則的比較

部分源碼 https://github.com/vuejs/vue/blob//src/core/vdom/patch.js#L501 如下：

在 reconcileChildren 函數的入參中

diff 的兩個主體是：oldFiber（current.child）和 newChildren（nextChildren，新的 ReactElement），它們是兩個不一樣的數據結構。

部分源碼

很多時候手工優化 dom 確實會比 virtual dom 效率高，對於比較簡單的 dom 結構用手工優化沒有問題，但當頁面結構很龐大，結構很復雜時，手工優化會花去大量時間，而且可維護性也不高，不能保證每個人都有手工優化的能力。至此，virtual dom 的解決方案應運而生。

virtual dom 是「解決過多的操作 dom 影響性能」的一種解決方案。

virtual dom 很多時候都不是最優的操作，但它具有普適性，在效率、可維護性之間達到平衡。

virutal dom 的意義：

vue2.x 的 diff 位於 patch.js 文件中，該演算法來源於 snabbdom，復雜度為 O(n)。了解 diff 過程可以讓我們更高效的使用框架。react 的 diff 其實和 vue 的 diff 大同小異。

最大特點：比較只會在同層級進行, 不會跨層級比較。

對比之前和之後：可能期望將 直接移動到

的後邊，這是最優的操作。

但是實際的 diff 操作是：

vue 中也使用 diff 演算法，有必要了解一下 Vue 是如何工作的。通過這個問題，我們可以很好的掌握，diff 演算法在整個編譯過程中，哪個環節，做了哪些操作，然後使用 diff 演算法後輸出什麼？

解釋：

mount 函數主要是獲取 template，然後進入 compileToFunctions 函數。

compileToFunction 函數主要是將 template 編譯成 render 函數。首先讀取緩存，沒有緩存就調用 compile 方法拿到 render 函數的字元串形式，在通過 new Function 的方式生成 render 函數。

compile 函數將 template 編譯成 render 函數的字元串形式。後面我們主要講解 render

完成 render 方法生成後，會進入到 mount 進行 DOM 更新。該方法核心邏輯如下：

上面提到的 compile 就是將 template 編譯成 render 函數的字元串形式。核心代碼如下：

compile 這個函數主要有三個步驟組成：

分別輸出一個包含

parse 函數：主要功能是 將 template 字元串解析成 AST（抽象語法樹） 。前面定義的 ASTElement 的數據結構，parse 函數就是將 template 里的結構（指令，屬性，標簽） 轉換為 AST 形式存進 ASTElement 中，最後解析生成 AST。

optimize 函數（src/compiler/optomizer.js）:主要功能是 標記靜態節點 。後面 patch 過程中對比新舊 VNode 樹形結構做優化。被標記為 static 的節點在後面的 diff 演算法中會被直接忽略，不做詳細比較。

generate 函數（src/compiler/codegen/index.js）:主要功能 根據 AST 結構拼接生成 render 函數的字元串 。

其中 genElement 函數（src/compiler/codgen/index.js）是根據 AST 的屬性調用不同的方法生成字元串返回。

總之：

就是 compile 函數中三個核心步驟介紹，

patch 函數 就是新舊 VNode 對比的 diff 函數，主要是為了優化 dom，通過演算法使操作 dom 的行為降低到最低， diff 演算法來源於 snabbdom，是 VDOM 思想的核心。snabbdom 的演算法是為了 DOM 操作跨級增刪節點較少的這一目標進行優化， 它只會在同層級進行，不會跨層級比較。

總的來說：

在創建 VNode 就確定類型，以及在 mount/patch 的過程中採用位運算來判斷一個 VNode 的類型，在這個優化的基礎上再配合 Diff 演算法，性能得到提升。

可以看一下 vue3.x 的源碼：https://github.com/vuejs/vue/blob//src/core/vdom/patch.js

對 oldFiber 和新的 ReactElement 節點的比對，將會生成新的 fiber 節點，同時標記上 effectTag，這些 fiber 會被連到 workInProgress 樹中，作為新的 WIP 節點。樹的結構因此被一點點地確定，而新的 workInProgress 節點也基本定型。在 diff 過後，workInProgress 節點的 beginWork 節點就完成了，接下來會進入 completeWork 階段。

snabbdom 演算法：https://github.com/snabbdom/snabbdom

定位：一個專注於簡單性、模塊化、強大功能和性能的虛擬 DOM 庫。

snabbdom 中定義 Vnode 的類型(https://github.com/snabbdom/snabbdom/blob//src/vnode.ts#L12)

init 函數的地址：

https://github.com/snabbdom/snabbdom/blob//src/init.ts#L63

init() 函數接收一個模塊數組 moles 和可選的 domApi 對象作為參數，返回一個函數，即 patch() 函數。

domApi 對象的介麵包含了很多 DOM 操作的方法。

源碼：

https://github.com/snabbdom/snabbdom/blob//src/init.ts#L367

源碼：

https://github.com/snabbdom/snabbdom/blob//src/h.ts#L33

h() 函數接收多種參數，其中必須有一個 sel 參數，作用是將節點內容掛載到該容器中，並返回一個新 VNode。

在 vue2.x 不是完全 snabbdom 演算法，而是基於 vue 的場景進行了一些修改和優化，主要體現在判斷 key 和 diff 部分。

1、在 snabbdom 中 通過 key 和 sel 就判斷是否為同一節點，那麼在 vue 中，增加了一些判斷 在滿足 key 相等的同時會判斷，tag 名稱是否一致，是否為注釋節點，是否為非同步節點，或者為 input 時候類型是否相同等。

https://github.com/vuejs/vue/blob//src/core/vdom/patch.js#L35

2、diff 差異，patchVnode 是對比模版變化的函數，可能會用到 diff 也可能直接更新。

https://github.com/vuejs/vue/blob//src/core/vdom/patch.js#L404

㈣ 如何使用源代碼構建一個可用的 Ubuntu 軟體包

用dpkg-source -x
foo.dsc從foo.orig.gz和foo.diff.gz創建工作目錄foo：一份發行版中立的源碼目錄，加上一個debian目錄以及目錄下的meta文件，就構成了一份可以生成二進制deb包的源碼工作目錄。其實從apt-get
source抓下來的目錄，已經是通過dpkg-source -x解壓過的了。dpkg-source
-x所做的主要事情就是1.解壓；2.把foo.diff.gz里的patch打到原始文件上。生成的foo目錄下的源文件，都已經是打過deb源碼包里的patch了的。
在foo目錄下，執行dpkg-buildpackage -us
-uc構建包。-us和-uc參數是不做簽名，適合於本地構建本地使用的情況。這個命令的輸出有兩個，一個是二進制deb包，另一個是源碼包，為什麼這里還要生成源碼包？因為你可能改動某些文件，那麼會生成新的diff.gz來記錄所有你針對原始源碼的改動，不管發布還是保存更改都更方便，下一次你只需要在生成的新的.dsc文件上執行dpkg-source -x就可以產生一個一模一樣的源碼了。如果你什麼都沒改動，那麼新產生的源碼包同你構建所來源的源碼包是一樣的。你也可以用參數-b和-S來控制這次構建只產生二進制包或者只產生源碼包。
兩個最重要的meta文件，debian/control和debian/rules。control文件決定了哪些二進制包將從這份源碼目錄中構建，一個源碼目錄往往是好幾個二進制包的輸入源。你不想生成哪個屏蔽它就行。二進制包的運行時依賴關系也在包的聲明中可見，並且control文件也聲明了構建過程中的依賴，不過可以給dpkg-buildpackage傳-d參數來忽略構建依賴。
debian/rules文件其實就是個Makefile，你可以執行make -f debian/rules target來單獨執行某個目標。rules文件里基本上都是對debhelper腳本函數的調用，像是dh_*這樣的函數，它們負責大部分的構建過程。常用的clean, install目標在rules文件中也有，有些基於源碼包的Makefile上所做的事情如make clean需要通過make -f debian/rules clean來代替。
和傳統意義的Make過程有點不一樣的就是，默認狀態下，每次dpkg-buildpackage，其實都是把從configure.ac生成configure腳本，到生成Makefile，到構建source，到安裝binary都做一遍，哪怕你並沒有改過configure.ac，或者改過源代碼.c文件，假如構建失敗了，就需要嘗試改動源代碼重新構建，有時候需要反復嘗試這個過程直到構建成功，如果包很大的話那需要花費的時間就很長，這時傳入-nc參數可以讓dpkg-buildpackage保留當前的構建結果，就像傳統的make一樣只會從出錯的地方重新開始。當然，當對源代碼的改動終止後，最後還是需要再執行一遍不帶-nc參數的命令」dpkg-buildpackage -us -uc」來重新完全構建一遍，否則在生成源碼包時可能會出錯。
dpkg-buildpackage不用擔心它會自動改變你的源文件（即通過dpkg-source
-x產生的文件），當然前提是你確實改動的是」源」文件，比如是configura.ac而不是configure，是dkms.conf.in而不是dkms.conf。
構建軟體時做得最多的事就是根據自己系統的需求調整./configure參數了吧，比如–enable–xxx或者–disable-xxx，在rules文件中，通過帶override前綴的target可以起到為默認的target定製參數的目的，如override_dh_auto_xconfigure:
對源碼包有修改最好通過dch -i來生成一個新的changelog文件，每個change item的title部分都是表示這次change的最新版本號，dpkg-buildpackage的輸出二進制包的版本號其實就是從changelog里提取的（不是寫在control文件里的）。