虚构 DOM 与 Diff 算法

1. 虚构 DOM
2. snabbdom
3. Vue 中的 Diff 算法

1 虚构 DOM

1. 概述
2. 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

1. 意识 snabbdom
2. h 函数
3. patch 函数
4. patchVnode 函数
5. updateChildren 函数
6. 总结

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 树的及时遍历及时比照及时更新来说，这种遍历思维并不适合。