关于javascript:大前端进阶Vuejs虚拟Dom及diff算法

虚构 DOM 就是一般的 js 对象，其能够用来形容 DOM 对象，然而因为不是真正的 DOM 对象，因而人们把它叫做虚构 DOM。

手动解决 DOM

在晚期的 js 利用中，开发人员须要手动解决 DOM，手动解决不仅代码繁琐，而且须要适配各种浏览器。

jQuery 操作 DOM

jQuery 对 DOM 解决操作进行了对立封装，由其外部解决浏览器的差别，尽管加重了开发人员的 DOM 操作老本，然而开发人员在开发时还是无奈防止 DOM 操作，无奈分心解决业务逻辑。

mvvm 框架屏蔽 DOM 操作

mvvm 框架解决了视图和状态之间的同步问题，让开发人员不再须要进行 DOM 操作。然而此时不能保留 DOM 状态，当更新代码时，会整体更新导致 DOM 状态失落。

虚构 DOM 晋升渲染能力

用操作虚构 DOM 来代替操作实在 DOM，不仅能够保留 DOM 状态，而且虚构 DOM 在更新时只会批改变动的 DOM，晋升了简单视图的渲染能力。

Snabbdom 是一个虚构 DOM 库，用其官网的话，其体积小，速度快，可扩大。Vue 框架虚构 DOM 应用的就是 Snabbdom（在其根底上进行了批改），上面将通过解析 Snabbdom 的源码来理解虚构 DOM 和 diff 算法。

上面的例子是应用 snabbdom 在页面上输入 hello world。

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>snabbdom-demo</title>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/snabbdom.js"></script>
    <script src="https://cdn.bootcss.com/snabbdom/0.7.3/h.js"></script>
</head>

<body>
    <div id="app"></div>
    <script>
        const patch = snabbdom.init([])
        const h = snabbdom.h
        let old = patch(document.querySelector('#app'), h('div.cls', 'hello world'))
        setTimeout(() => {patch(old, h('div.cls', 'hello snabbdom'))
        }, 2000);
    </script>
</body>

</html>

从上例能够看出，snabbdom 在应用的时候蕴含如下两个步骤：

调用 init 生成 patch 函数，init 反对传入一个数组，数组中能够蕴含扩大模块。
调用 patch 函数对页面 dom 进行比照更新，patch 承受 dom 元素或者 h 函数生成的 vnodes。

h 函数最早见于 hyperscript，用于应用 JavaScript 创立超文本。在 snabbdom 中，h 函数用于生成 vnodes。

其实在应用 Vue 的我的项目中，就能够看到 h 函数：

new Vue({
    router,
    store,
    render: h => h(App)
}).$mount('#app')

此处 h 函数的作用就是将组件转换为 vnodes。

源码：

export function h(sel: string): VNode
export function h(sel: string, data: VNodeData | null): VNode
export function h(sel: string, children: VNodeChildren): VNode
export function h(sel: string, data: VNodeData | null, children: VNodeChildren): VNode
export function h(sel: any, b?: any, c?: any): VNode {
    // .....
    // 对传入的参数进行解决，最终调用 vnode 办法生成 vnode 对象
    return vnode(sel, data, children, text, undefined)
};


export 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}
}

h 函数的源码在去除参数判断之后其实非常简单，就是将解决后的用户传参转换为一个 vnode 对象。

const patch = snabbdom.init([])

从 init 函数的应用就能够看出，其是一个高阶函数，因为其返回一个函数。

在 snabbdom 库中，init 函数用于解决模块，指定 dom 操作 api 及生成回调函数对象 cbs 用于后续 patch 函数应用。

源码：

// modules：模块数组，用于传入扩大模块
// domapi：定义如何操作 dom，通过批改 domapi，能够让 snabbdom 库反对小程序等利用
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
    let i: number
    let j: number

    // 收集所有的生命周期钩子函数
    const cbs: ModuleHooks = {create: [],
        update: [],
        remove: [],
        destroy: [],
        pre: [],
        post: []}

    // 为 api 增加默认值
    const api: DOMAPI = domApi !== undefined ? domApi : htmlDomApi

    // 遍历所有生命周期
    for (i = 0; i < hooks.length; ++i) {cbs[hooks[i]] = []
        // 遍历所有模块，如果模块定义了生命周期钩子函数，那么将对应函数增加到 cbs 中
        for (j = 0; j < modules.length; ++j) {const hook = modules[j][hooks[i]]
            if (hook !== undefined) {(cbs[hooks[i]] as any[]).push(hook)
            }
        }
    }

    // ...... 省略一些外部函数

    // 返回 patch 函数
    return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {// ......}
}

在解说 patch 函数之前，须要理解一些工具函数：

`isVnode`

用于判断一个 js 数据是否是 vnode，只须要判断对象是否蕴含 sel 属性（在应用 h 函数生成的 vnode 对象均蕴含 sel 属性），

function isVnode (vnode: any): vnode is VNode {return vnode.sel !== undefined}

`sameVnode`

用于判断两个 vnode 是否雷同，在 snabbdom 中，如果两个 vnode 的 key 和 sel 属性雷同，那么就认为这两个 vnode 雷同。

function sameVnode (vnode1: VNode, vnode2: VNode): boolean {return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel}

patch 函数是 snabbdom 库的外围函数，在其外部执行新旧 Vnode 之间的比照，并依据比照的差别更新实在 DOM，执行实现后，会返回新的 Vnode 作为下次比照的旧 Vnode。

patch 的执行过程分为如下几步：

第一步：执行所有的 pre 生命钩子函数。

第二步：用 isVnode 函数判断传入的 oldVnode 是否是一个 Vnode 对象。

不是 Vnode 对象，将 oldVnode 转换成空的 Vnode 对象。

第三步：用 sameVnode 函数判断 oldVnode 和 newVnode 是否雷同。

如果雷同，调用 patchVnode 进行比照更新。
如果不雷同，间接删除 oldVnode，将 newVnode 渲染成 dom 增加到页面上。

第四步：执行 insert 和 post 生命钩子函数。

function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node
    const insertedVnodeQueue: VNodeQueue = []
    // 1. 执行 pre 钩子函数
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]()

    // 2. 判断 oldVnode 是否是 Vnode
    if (!isVnode(oldVnode)) {oldVnode = emptyNodeAt(oldVnode)
    }

    // 3. 判断 oldVnode 和 newVnode 是否雷同
    if (sameVnode(oldVnode, vnode)) {
        // 如果雷同就比照更新
        patchVnode(oldVnode, vnode, insertedVnodeQueue)
    } else {
        // 如果不同就替换
        elm = oldVnode.elm!
        parent = api.parentNode(elm) as Node
        // 依据 Vnode 创立 dom
        createElm(vnode, insertedVnodeQueue)

        if (parent !== null) {api.insertBefore(parent, vnode.elm!, api.nextSibling(elm))
            removeVnodes(parent, [oldVnode], 0, 0)
        }
    }

    // 4. 执行 insert 和 post 生命钩子函数
    for (i = 0; i < insertedVnodeQueue.length; ++i) {insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i])
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]()
    return vnode
}

patchVnode 函数的作用是比照新旧 Vnode 之间的差别，并依据差别操作实在 dom。

patchVnode 函数的执行过程能够分为以下 4 步：

第一步：执行用户设置的 prepatch 钩子函数。

第二步：执行 update 钩子函数，先执行模块的 update 函数，再执行用户设置的 update 函数。

第三步：判断 newVnode 的 text 属性是否被设置。

设置了 text 属性，如果 oldVnode 和 newVnode 的 text 属性值不雷同，那么首先删除 oldVnode 的所有子节点，而后批改 oldVnode 对应的 ele 元素的文本内容。
未设置 text 属性

如果 oldVnode.children 和 newVnode.children 都有值
调用 updateChildren()
应用 diff 算法比照子节点，更新子节点
如果 newVnode.children 有值，oldVnode.children 无值
清空 DOM 元素
调用 addVnodes()，批量增加子节点
如果 oldVnode.children 有值，newVnode.children 无值
调用 removeVnodes()，批量移除子节点
如果 oldVnode.text 有值
清空 DOM 元素的内容

第四步：执行用户设置的 postpatch 钩子函数。


function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    const hook = vnode.data?.hook
    // 1. 执行用户设置的 prepatch 钩子函数
    hook?.prepatch?.(oldVnode, vnode)
    const elm = vnode.elm = oldVnode.elm!
    const oldCh = oldVnode.children as VNode[]
    const ch = vnode.children as VNode[]
    if (oldVnode === vnode) return
    if (vnode.data !== undefined) {
        // 2. 执行 update 钩子函数
        for (let i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode)
        vnode.data.hook?.update?.(oldVnode, vnode)
    }
    // 3. 判断 vnode 的 text 属性是否被定义
    if (isUndef(vnode.text)) {
        // 二者都有 children
        if (isDef(oldCh) && isDef(ch)) {if (oldCh !== ch) updateChildren(elm, oldCh, ch, insertedVnodeQueue)
        }
        // vnode 有 children，oldVnode 没有 
        else if (isDef(ch)) {if (isDef(oldVnode.text)) api.setTextContent(elm, '')
            addVnodes(elm, null, ch, 0, ch.length - 1, insertedVnodeQueue)
        }
        // oldVnode 有 children，vnode 没有 
        else if (isDef(oldCh)) {removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        }
        // 都没有 children，oldVnode 有 text
        else if (isDef(oldVnode.text)) {api.setTextContent(elm, '')
        }
    }
    // vnode 的 text 属性被定义并且和 oldVnode 的 text 属性值不同
    else if (oldVnode.text !== vnode.text) {
        // 如果 oldVnode 蕴含子元素
        if (isDef(oldCh)) {removeVnodes(elm, oldCh, 0, oldCh.length - 1)
        }
        // 设置文本节点内容
        api.setTextContent(elm, vnode.text!)
    }
    // 4. 执行用户设置的 postpatch 钩子函数
    hook?.postpatch?.(oldVnode, vnode)
}

diff 算法 的外围办法，同层比拟新旧节点 children 之间的差别并更新 dom。

比照节点差别就是比照两个 dom 树之间的差别。

一般形式

获取第一颗树的每个节点和第二棵树的每一个节点进行比对，这样比对的工夫复杂度为 O(n^l)，l 示意树节点的层级数，如果一棵树的层级是 3，那么复杂度就是 O(n^3)

同层比照

因为在操作 dom 的时候，很少会将一棵 dom 树的父节点挪动更新到其子节点。因而，在比照时，只须要找两棵 dom 树的同级别子节点顺次比照，比对实现后而后再找下一级别的节点进行比对，这样的工夫复杂度为 O(n)。

因为虚构 Dom 的 diff 算法是同层比照两棵 dom 树，因而探索 diff 算法过程，也就是探索某一层级两组节点数组之间的比照过程。

diff 算法能够大抵分成两个步骤，以上面的两个数组为例：

let oldNodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
let newNodes = ['A', 'H', 'F', 'B', 'G']

此步骤目标是依据新的数组，将旧的数组重新排列，新数组中的每一项在旧数组中无外乎两种状况：

旧数组中存在，调整其到正确地位

如 newNodes 数组中的 B 项在 a 数组中存在，然而 oldNodes 数组中其地位不正确，根据 newNodes 数组的构造，B应该在 F 与G之间，因而须要调整 B 的地位。

旧数组不存在，在正确地位插入

如 newNodes 数组中的 H 在 oldNodes 数组中不存在，所以须要将其插入到 oldNodes 数组中，那么插入到哪个地位？依据 newNodes 的构造，应该将 H 插入到 A 的前面。

调整实现之后，oldNodes 应该变成如下：

let oldNodes = ['A', 'H', 'C', 'D', 'E', 'F', 'B', 'G']

整个步骤一通过一个循环就能够实现，将两个数组的开始、完结索引作为循环变量，每调整一次数组（挪动或者新增），就批改变量指向的索引，直到某一个数组的开始变量大于完结变量，那么阐明此数组中的每一个元素都被遍历过，循环完结。

设置循环开始的批示变量

let oldStartIdx = 0
let oldEndIdx = oldCh.length - 1
let oldStartVnode = oldCh[0]
let oldEndVnode = oldCh[oldEndIdx]

let newStartIdx = 0
let newEndIdx = newCh.length - 1
let newStartVnode = newCh[0]
let newEndVnode = newCh[newEndIdx]

用 8 个变量别离存储：
旧数组：开始索引，开始节点，完结索引，完结节点。
新数组：开始索引，开始节点，完结索引，完结节点。

设置循环执行条件

while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {// 调整逻辑}

当某个数组的开始索引变量大于完结索引变量时，循环完结。

调整逻辑

将旧数组的开始完结节点和新数组的开始完结节点进行比照，会呈现以下 5 种状况：

新旧数组的开始节点雷同

此种状况下，阐明旧数组中以后开始节点变量存储的开始节点地位是正确的，不须要挪动。

if (sameVnode(oldStartVnode, newStartVnode)) {
    // 递归 diff 解决子节点
    patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue)
    // 将起始节点，起始索引向后挪动一位
    oldStartVnode = oldCh[++oldStartIdx]
    newStartVnode = newCh[++newStartIdx]
}

新旧数组的完结节点雷同

此种状况下，阐明旧数组中以后完结节点变量存储完结节点地位是正确的，不须要挪动。

if (sameVnode(oldEndVnode, newEndVnode)) {patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue)
    // 将完结节点，完结索引向前挪动一位
    oldEndVnode = oldCh[--oldEndIdx]
    newEndVnode = newCh[--newEndIdx]
}

旧数组的开始节点和新数组的完结节点雷同

此种状况下，阐明旧数组中的以后开始节点变量存储的开始节点地位不正确，应该调整到以后旧数组完结节点变量存储的完结节点之后。

也能够用上面的例子示意此种状况：

let oldNodes = ['A', 'B', 'C']
let newNodes = ['D', 'A']

oldNodes 数组中的开始节点 A 和 newNodes 的完结节点 A 雷同，此时，如果根据 newNodes 来调整 oldNodes，须要将 A 挪动到 C 的前面。挪动实现后，oldNodes 应该变成：['B', 'C', 'A']。

if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
    patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue)
    // 调整开始节点的地位，将其挪动到完结节点的前面
    api.insertBefore(parentElm, oldStartVnode.elm!, api.nextSibling(oldEndVnode.elm!))
    // 此时旧数组中的开始节点曾经被解决了，须要将开始索引指向下一位
    oldStartVnode = oldCh[++oldStartIdx]
    // 此时新数组中的完结节点相当于被解决了，须要将完结索引指向前一位
    newEndVnode = newCh[--newEndIdx]
}

旧数组的完结节点和新数组的开始节点雷同

此种状况下，阐明旧数组中以后的完结节点变量存储的完结节点地位不正确，应该将其挪动到旧数组以后开始节点变量存储的开始节点之前。

也就是：

let oldNodes = ['A', 'B', 'C']
let newNodes = ['C', 'D']

将 oldNodes 调整为['C', 'A', 'B']

if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
    patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue)
    // 将完结节点挪动到开始节点之前
    api.insertBefore(parentElm, oldEndVnode.elm!, oldStartVnode.elm!)
    // 旧数组中的完结节点指向前一位
    oldEndVnode = oldCh[--oldEndIdx]
    // 新数组中的开始节点指向后一位
    newStartVnode = newCh[++newStartIdx]
}

以上状况均不合乎

在这种状况下，只须要判断新数组初始节点在旧数组中是否存在，如果不存在，就在旧数组开始节点之前插入新数组的开始节点。如果存在，就将对应的节点挪动到旧数组开始节点之前。

如：

let oldNodes = ['A', 'B', 'D', 'C']
let newNodes = ['D', 'E']

newNodes 的开始节点为 D，其在 oldNodes 数组中存在，所以将D 挪动到 A 节点之前，变为：['D', 'A', 'B', 'C']。

if (oldKeyToIdx === undefined) {
    // 创立 key 与索引值的构造数组，不便查找
    oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx)
}
// 依据新数组的初始节点在旧数组中查找
idxInOld = oldKeyToIdx[newStartVnode.key as string]
// 不存在
if (isUndef(idxInOld)) { 
    // 创立一个和新数组开始节点雷同的 dom 节点，插入到旧数组开始节点之前
    api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
} 
// 存在
else {
    // 获取旧数组中以后须要挪动的节点
    elmToMove = oldCh[idxInOld]
    // 如果 sel 不一样，同样认为不同，和不存在的解决逻辑一样
    if (elmToMove.sel !== newStartVnode.sel) {api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm!)
    } else {patchVnode(elmToMove, newStartVnode, insertedVnodeQueue)
        // 将旧数组原有地位的元素置空
        oldCh[idxInOld] = undefined as any
        // 将须要挪动的节点挪动到旧数组初始节点之前
        api.insertBefore(parentElm, elmToMove.elm!, oldStartVnode.elm!)
    }
}
// 将新数组的初始索引向后挪动一位
newStartVnode = newCh[++newStartIdx]

通过步骤一的解决，可能会呈现两种状况：

新数组被遍历完，旧数组没有遍历完。

如下例：

let oldNodes = ['A', 'B', 'C']
let newNodes = ['A', 'E']

步骤一实现之后，oldNodes 数组变为 ['A', 'E', 'B', 'C']，此时 B 和C没有被遍历到。

在这种状况下，阐明 B 和C在新数组中不存在，间接删掉即可。

旧数组被遍历完，新数组没有遍历完。

如下例：

let oldNodes = ['A']
let newNodes = ['A', 'D', 'E']

步骤一实现后，oldNodes 数组仍然为 ['A']，此时 newNodes 数组中的D 和E还没有被遍历到。

在这种状况下，阐明 D 和E是新增的元素，在旧数组中必定没有，间接将两个元素减少到相应地位即可。

步骤二实现逻辑

// oldStartIdx <= oldEndIdx 代表旧数组中有元素没有被遍历到
// newStartIdx <= newEndIdx 代表新数组中有元素没有被遍历到
if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) {
    // 如果新数组中有残余元素
    if (oldStartIdx > oldEndIdx) {before = newCh[newEndIdx + 1] == null ? null : newCh[newEndIdx + 1].elm
        // 间接将其增加到旧数组的相应地位。addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue)
    } else {
        // 如果旧数组中有残余元素
        // 间接在旧数组中将其删除
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx)
    }
}

snabbdom 为了保障框架的简洁高效，将款式、属性、事件等交给模块解决。

模块的定义非常简单，常见的就是在 create 和 update 生命周期钩子函数中依据用户输出批改 dom 节点。

以 updateAttrs 模块为例：

function updateAttrs (oldVnode: VNode, vnode: VNode): void {
   // 比照批改两个 vnode 对应 ele 的 attrs
   // ......
}

// 导出一个蕴含 create，update 钩子函数的对象，在 init 的时候，会将钩子函数增加到 cbs 中。export const attributesModule: Module = {create: updateAttrs, update: updateAttrs}

关于javascript:大前端进阶Vuejs虚拟Dom及diff算法

何为虚构 DOM

为何呈现虚构 DOM

Snabbdom

根本应用

h 函数

init 函数

工具函数

`isVnode`

`sameVnode`

patch 函数

patchVnode

updateChildren

一般比照 vs 同层比照

diff 过程

步骤一重新排列旧的数组

步骤一实现逻辑

步骤二解决重新排列后的数组

步骤二实现逻辑

模块

何为虚构 DOM

为何呈现虚构 DOM

Snabbdom

根本应用

h 函数

init 函数

工具函数

isVnode

sameVnode

patch 函数

patchVnode

updateChildren

一般比照 vs 同层比照

diff 过程

步骤一 重新排列旧的数组

步骤一实现逻辑

步骤二 解决重新排列后的数组

步骤二实现逻辑

模块

`isVnode`

`sameVnode`

步骤一重新排列旧的数组

步骤二解决重新排列后的数组