【vue】虛擬DOM與Diff算法詳情 - vue.js,虛擬dom,diff,virtual-dom 懟懟博客

虛擬DOM與Diff算法

虛擬DOM
snabbdom
Vue中的Diff算法

1 虛擬DOM

概述
VNode

1.1 概述

原生DOM為我們提供了一些獲取DOM元素以及操作DOM元素的API，可以對DOM元素進行增刪改查。
複雜的頁面狀態維護需要提前寫好大量的DOM操作，會造成狀態很難維護，代碼的邏輯也很混亂。
所以我們會使用數據驅動的方式進行視圖更新 - 數據與視圖的綁定，更新數據時進行視圖更新。

渲染
我們通常以狀態作為輸入，並生成DOM輸出到頁面上顯示 - 渲染

問題
當狀態發生變化時，需要重新渲染，也就是重新輸入與輸出，那麼應該如何確認狀態發生了什麼變化，又該如何更新DOM？
顯然把DOM全部刪除再重新生成是不可取的。

解決方案
Angular採用髒檢查的方式：設置一些觸發條件，執行一個檢測來遍歷所有的數據，對比更改的位置執行更新的操作，性能低
React與Vue採用虛擬DOM：根據狀態生成一個虛擬節點樹，使用虛擬節點樹進行渲染。數據變化時，創建一個新的虛擬節點樹，對兩棵樹進行對比只渲染不同的部分。

Vue虛擬節點樹是由組件樹建立起來的整個虛擬節點(Virtual Node - vnode) 樹

React與Vue對比
首先兩者的虛擬DOM是一致的，diff算法只有細微區別，但是更新策略大不相同
React：函數式組件思想當狀態變化會遍歷diff當前組件所有子節點組件，react 16引入fiber，可以使用API進行中斷，避免不必要的子組件重新渲染
Vue：組件響應式思想代理模式將data中的值用setter/getter綁定起來，並設置響應式watcher，當狀態變化時會通知到組件，在組件中diff

Vue中的虛擬DOM
使用模板描述狀態與DOM之間的映射關係。
通過編譯將模板轉換成渲染函數，渲染函數會返回一個虛擬節點樹，然後patch到視圖
在patch的過程中會對新舊vnode進行對比，根據對比結果進行DOM操作來更新視圖

1.2 VNode

VNode類可以實例化出不同類型的vnode實例，代表不同類型的DOM元素

1.2.1 VNode類

  var VNode = function VNode (
    tag,
    data,
    children,
    text,
    elm,
    context,
    componentOptions,
    asyncFactory
  ) {
    this.tag = tag;
    this.data = data;
    this.children = children;
    this.text = text;
    this.elm = elm;
    this.ns = undefined;
    this.context = context;
    this.fnContext = undefined;
    this.fnOptions = undefined;
    this.fnScopeId = undefined;
    this.key = data && data.key;
    this.componentOptions = componentOptions;
    this.componentInstance = undefined;
    this.parent = undefined;
    this.raw = false;
    this.isStatic = false;
    this.isRootInsert = true;
    this.isComment = false;
    this.isCloned = false;
    this.isOnce = false;
    this.asyncFactory = asyncFactory;
    this.asyncMeta = undefined;
    this.isAsyncPlaceholder = false;
  };

實例化後產生的vnode可以理解為節點描述對象，它描述了應該如何創建真實DOM節點。通過vnode創建DOM，再插入到視圖中這是渲染視圖的基本過程。

<!-- 真實頁面 -->
<div id="app" class="container">
    <h1>虛擬DOM</h1>
    <ul style="color:teal">
        <li>項目一</li>
        <li>項目二</li>
    </ul>
</div>

//對應的vnode描述對象
{
    tag: 'div',
    props: { id: 'app', className: 'container' },
    children: [
        { tag: 'h1', children: '虛擬DOM' },
        {
            tag: 'ul',
            props: { style: 'color: teal' },
            children: [
                { tag: 'li', children: '項目一' },
                { tag: 'li', children: '項目二' },
            ]
        }
    ]
}

vnode會被緩存起來，方便前後對比靈活的修改真實DOM

1.2.2 VNode的類型

vnode的類型有以下幾種

註釋節點
文本節點
元素節點
組件節點
函數式組件
克隆節點

註釋節點

//創建註釋節點
function createEmptyVode(text) {
    const node = new VNode()
    node.text = text
    node.isComment = true
    return node
}

文本節點

//創建文本節點
function createTextVNode(val){
    return new VNode(undefined,undefined,undefined,String(val))
}

克隆節點

function cloneVNode(vnode,deep){
    const cloned = new VNode(vnode.tag,vnode.data,...)
    cloned.ns = vnode.ns
    ...

    cloned.isCloned = true
    if(deep && vnode.children){
        cloned.children = cloneVNode(vnode.children)
    }
    return cloned
}

唯一區別isCloed

元素節點

tag：標籤名
data：節點數據，attrs、class、id、style...
children：子節點數組
context：當前組件實例vm

組件節點
與元素節點類似，還有兩個獨有的屬性

componentOptions：組件節點的選項參數，propsData、tag、children...
componentInstance：組件實例

//一個組件節點
<child></child>
//vnode
{
    ...
    tag:"vue-component-1-child"
}

函數式組件
與組件節點類似，還有兩個獨有的屬性

functionalContext：函數式上下文
functionalOptions：函數式選項

2 snabbdom

認識snabbdom
h函數
patch函數
patchVnode函數
updateChildren函數
總結

2.1 認識snabbdom

snabbdom是著名的虛擬DOM庫，是diff算法的鼻祖，Vue源碼借鑑了snabbdom。
倉庫地址
snabbdom庫是使用TypeScript寫的，github上只有TypeScript的版本
可以在npm上安裝編譯成JavaScript的庫文件，同時也包含了原版文件

npm init
npm install -S snabbdom

可以在node_modules/snabbdom的build文件夾下查看js版本，在src文件夾下查看ts版本

容器與引入

//容器與按鈕
<div id="container"></div>
<button id="btn">修改數據</button>

//引入snabbdom
<script src="https://lib.baomitu.com/snabbdom/0.7.4/h.js"></script>
<script src="https://lib.baomitu.com/snabbdom/0.7.4/snabbdom-class.js"></script>
<script src="https://lib.baomitu.com/snabbdom/0.7.4/snabbdom-eventlisteners.js"></script>
<script src="https://lib.baomitu.com/snabbdom/0.7.4/snabbdom-props.js"></script>
<script src="https://lib.baomitu.com/snabbdom/0.7.4/snabbdom-style.js"></script>
<script src="https://lib.baomitu.com/snabbdom/0.7.4/snabbdom.js"></script>
<script src="index.js"></script>

初始化與生成虛擬節點

/**
 * 初始化
 */
// 引入snabbdom庫
const snabbdom = window.snabbdom
// 初始化h函數 - 創建虛擬節點
const h = snabbdom.h
// 初始化patch函數 - 將虛擬節點插入指定容器中
const patch = snabbdom.init([
    snabbdom_class,
    snabbdom_props,
    snabbdom_style,
    snabbdom_eventlisteners
])

/**
 * 生成虛擬節點並插入
 */
//獲取容器
const container = document.getElementById('container')
//創建vnode 
const vnode = h('ul#list', {}, [
    h('li.item', {}, '第一項'),
    h('li.item', {}, '第二項'),
])
//插入vnode
patch(container, vnode)

使用h函數生成vnode
patch(oldVnode,newVnode)對新舊虛擬節點樹進行比較，得到需要修改的信息，最終去操作DOM更新視圖

patch操作

const btn = document.getElementById('btn')
btn.addEventListener('click', () => {
    const newVnode = h('ul#list', {}, [
        h('li.item', {}, '項目一'),
        h('li.item', {}, '項目2'),
        h('li.item', {}, '項目3'),
    ])
    patch(vnode, newVnode)
    vnode = newVnode
})

這裏手動創建新的vnode，然後使用patch進行對比計算
在Vue中會有數據偵測，數據變化會識別組件然後自動調用渲染函數，以及後續操作
可以看到數據更新與添加都會觸發節點的重新渲染

2.2 h函數

生成vnode

下面代碼描述都是精簡之後的，詳細訪問源碼倉庫

核心邏輯

//核心邏輯
function h(sel:string,data:VNodeData|null,children:VNodeChildren):VNode;
function h(sel:any,b?:any,c?:any):VNode {
    //設置判斷條件確定 data children text
    ...
    return vnode(sel,data,children,text,undefined)
}
//vnode函數
function vnode(
    sel: string | undefined,
    data: any | undefined,
    children: Array<VNode | string> | undefined,
    text: string | undefined,
    elm: Element | Text | undefined
): VNode {
    const key = data === undefined ? undefined : data.key;
    //返回vnode節點
    return {sel, data, children, text, elm, key}
}

elm 對應的真實DOM
每個組件都可以接收key，在v-for中必須提供key
children與text是互斥的，newVNode兩者有其一，就需要刪除對應的或者更新自身

2.3 patch函數

將vnode渲染成真實DOM

2.3.1 init

//init 返回patch函數
function init(moudles: Array<Partial<Module>>,domApi?:DOMAPI){
    function emptyNodeAt(elm:Element)
    function createRmCb(childElm: Node,listeners: number)
    function createElm(vnode: VNode, insertedVnodeQueue: VNode): Node{...}
    function addVnodes(
        parentElem:Node,
        before:Node|null,
        vnodes:VNode[],
        startIdx:number,
        endIdx:number,
        insertedVnodeQueue:VNodeQueue
    )
    function invokeDestoryHook(vnode: VNode)
    function removeVnodes(
        parentElem: Node,
        vnodes: VNode[],
        startIdx: number,
        endIdx: number
    ): void {...}

    function updateChildren(...){...}
    function patchVnode(...){...}
    return function patch(...): VNode{... return vnode}
}

init接收兩個數據，返回一個patch函數

2.3.2 patch函數

基本結構

function patch(oldVnode: VNode|Element,vnode: VNode):VNode{
    //判斷oldVnode類型，決定是否創建空的vnode - 首次渲染
    oldVnode是Element -> oldVnode emptyNodeAt(oldVode)

    /**
     * 對比oldVnode與vnode的sel和key是否相等
     * sameVnode(oldVnode,vnode)
     */
    //相等時 - 同一個節點 更新
    pathchVnode(oldVnode,vnode,insertedVnodeQueue)

    //不相等時 - 不是同一個節點 - 創建並插入
    //獲取需要更新的DOM
    elm = oldVnode.elm!
    parent = api.parentNode(elm) as Node
    //根據vnode創建真實DOM節點
    createElm(vnode,insertedVnodeQueue)
    //插入至真實DOM
    if (parent !== null) {
      api.insertBefore(parent, vnode.elm!, api.nextSibling(elm));
      //刪除原DOM節點
      removeVnodes(parent, [oldVnode], 0, 0);
    }
}

emptyNodeAt

function emptyNodeAt(elm:Element){
    const id = elm.id ? "#" + elm.id : ""
    cosnt c = elm.className ? "." + elm.className.split("").join(".") : ""
    return vnode(api.tagName(elm).toLowerCase() + id + c,{},[],undefined,elm)
}

返回一個vnode，參數1是一個選擇器(標籤名#id.class) 指定真實DOM最後一個參數elm

2.4 patchVnode函數

針對新舊相同節點進行更新 - 更新vnode以及視圖

function patchVnode(
    oldVndoe: VNode,
    vnode: VNode,
    insetedVnodeQueue:VNodeQueue
){
    ...
    //設置vnode關聯的DOM元素
    const elm = (vnode.elm = oldVnode.elm)!
    //獲取children 新舊相等則不更新
    cosnt oldCh = oldVnode.children as VNode[]
    cosnt ch = vnode.children as VNode[]
    if(oldVnode === vnode) return
    ...
    /**
     * if 新無text
     */
    //if 新有children 老有children 
    updateChildren(...)

    //else if 新有children -> 老無children/有text或無text
    api.setTextContent(elm,'') //清空text
    addVodes(elm,null,ch,0,ch.length-1,insetedVnodeQueue)//添加children

    //else if 老有children -> 新無children text
    removeVnodes(elm,oldCh,0,oldCh.length-1) //移除children 新的什麼都沒有
    
    //else if 老有text -> 新無children text
    api.setTextContent(elm,'')//清空text

    /**
     * else if 新老text不等 -> 相等結束判斷
     */
    // if 老有children -> 新有text
    removeVnodes(elm,oldCh,0,oldCh.length-1)//移除children

    api.setTextContent(elm,vnode.text)//設置text
}

patchNode在兩節點指代同一個DOM是，對其text與children進行判斷比較
不管是oldVnode還是newVnode，text與children是互斥的，只能有其一
根據這種關係理論上有9中組合，除去新舊兩者都無，剩餘8種，上述的判斷條件以及處理程序完全涵蓋了所有操作。

主要關注新vnode的狀態，比對後決定了應該進行怎麼的DOM操作
添加children，移除children，設置text，清空text

2.5 updateChildren函數

patchVnode中兩者都都children時進行的處理函數

function updateChildren(
    parentElm: Node,
    oldCh: VNode[],
    newCh: VNide[],
    insertedVnodeQueue: VNodeQueue
){
    //索引 - 首尾共4個
    let oldStartIdx = 0    , oldEndIdx = oldCh.length - 1;//標記為o1 o2號指針
    let newStartIdx = 0 , newEndIdx = newCh.length - 1;//標記為n1 n2號指針
    //節點 - 首尾共4個
    let oldStartVnode = oldCh[0] , oldEndVnode = oldCh[oldEndIdx]//標記為oA oB
    let newStartVnode = newCh[0] , newEndVnode = oldCh[newEndIdx]//標記為nA nB  
    //其他
    let oldKeyToIdx: KeyToIndexMap | undefined

    /**
     * 雙指針循環遍歷，當首尾指針前後順序發生變化時終止
     */
    while(oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx){
        //if oA == null  o1 oA 右移
        ...其餘判空操作
        
        //4中比較
        //else if sameVnode(oA,nA) - 兩首節點使用同一個DOM
        patchVnoe(oA,nA) //同時將兩首指針首節點右移
        ...尾節點同理
        
        //else if sameVnode(oB,nA) - 新首老尾使用同一個DOM
        patchVnode(oB,oA) //同時將兩首指針首節點右移
        api.insetBefore(parentElm,oA.elm!,api.nextSibling(oB.elm!))//需要移動    

        //else 4種比較均未命中
          idxInOld = oldKeyToIdx[nA.key as string]//拿到新首節點的key

          //if 老children無相同key - 全新的vnode
          api.insertBefore(parentElm,createElm(nA,...),oA.elm!)//創建新節點

          //else 有相同的key
            elmToMove = oldCh[idxInOld]//獲取
              //if tag不相等 - 全新的vnode
            ...同上創建新節點並插入

            //else tag相等 - 等價於sameVnode()
            patchVnode(oldV,oA,insetedVnodeQueue)
            oldCh[idxInOld] = undefined as any
            api.insertBefore(parentElm,elmToMove.elm!,oB.elm!)//重新插入

          //新首節點右移     
    }
    //收尾工作
    if(o1 <= o2 || n1 <= n2 ){// 有一個遍歷結束
        if(o1 > o2){//老children先結束 -> 新節點未完全遍歷，有新增
            before = newCh[n2 + 1] == null ? null : newCh[n2 + 1].elm
            addVnodes(parentElm,before,newCh,n1,n2,insertedVnodeQueue)    
        } else{//新children未完全遍歷 - 有刪除
            removeVnodes(parentElm,oldCh,o1,o2)
        }
    }
}

流程

創建新舊children的首尾索引與對應節點
雙指針循環，當兩個中有一個的首尾指針順序變化循環結束
進行首首，尾尾，首尾比較，key與sel相同，進行patchVnoe並移動兩個指針與節點
未命中，從新children的首節點開始，去匹配舊children的key，再檢測tag，以此判斷是新增還是移動，移動首指針與節點
繼續循環，四種比較與單獨的key、sel移動一個指針節點
循環結束，如果有一方未完全遍歷完成，判斷是刪除了節點還是添加了節點，並對DOM進行修改

2.6 總結

從整個流程來看，snabbdom對於整個虛擬節點樹進行了層序遍歷的diff
從根節點開始對children進行遍歷比較，只比較同一層的同父節點的子節點。這種遍歷的思想也稱為廣度優先遍歷

樹的先序遍歷或者説深度優先遍歷會向着一個子節點的一個方向一直遍歷下去，對於dom樹的及時遍歷及時對比及時更新來説，這種遍歷思想並不合適。