虚构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 initnpm 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', {}, '第二项'),])//插入vnodepatch(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树的及时遍历及时比照及时更新来说，这种遍历思维并不适合。