虚拟dom算法解析

2018-05-19 阅读 1840 收藏 3 原链:github.com
分享到:

前端必备图书《Web应用安全权威指南》 >> >> 

前言

snabbdom是一个虚拟dom算法库,它的特点是效率高、可扩展,许多开源项目采用了这种算法,例如vue。本文试图还原虚拟dom的diff原理(仅限于snabbdom算法)。

虚拟dom

什么是虚拟dom

首先需要了解什么是虚拟dom,虚拟dom是真实dom的简单映射。我们知道一个真实dom的属性是十分繁多的,但是表示一个真实dom仅仅需要一部分属性就够了。对于一个真实dom,只要我们清楚它的选择器、它的子节点以及它的“数据”(属性、样式、类、事件等),我们就可以利用一个对象(即虚拟dom)来描述这个真实的dom节点,如下:

class Vnode {
    constructor({sel, data, children, text, key}) {
        //  选择器
        this.sel = sel;
        //  key
        this.key = key;
        //  保存属性、样式等
        this.data = data;
        //  子节点
        this.children = children;
        //  对应的真实dom节点
        this.elm = null;
        //  文本节点
        this.text = text;
    }
}

举个例子

<ul>
    <li>a</li>
    <li>b</li>
</ul>

可以被表示为:

new Vnode({
    sel: 'ul',
    children: [
        new Vnode({
            sel: 'li',
            children: [new Vnode({text: a})]
        }),
        new Vnode({
            sel: 'li',
            children: [new Vnode({text: b})]
        })
    ]
})

为什么需要虚拟dom

对于前端mvc模型,当model改变时相应的view需要更新,一种最简单的方法是只要model发生了改变就利用模板引擎更新整个view,这在页面简单时是极好的,但是当面对复杂应用时代价过大,其需要重新渲染dom树,这可是很耗时的。合理的操作是哪里改变了重新渲染哪里,通过比较新旧虚拟dom树可以找出相同和不同,相同的地方就复用真实dom节点,不同的地方就对真实dom节点进行增加、删除、移动等操作,这样一来就大大提高了效率。 img

虚拟dom的diff

在谈到虚拟dom的diff时有个前提:diff只发生在相同的层级。这是因为跨越层级的dom增添、删除、移动并不常见,一般都是兄弟节点之间的位置发生变化。

img

首先需要判断两个虚拟节点是否为samaVnode,假如是sameVnode则保留旧的真实dom并对新旧虚拟节点的children进行diff,否则删除掉旧虚拟节点对应的真实dom并替换为新虚拟节点对应的真实dom。如下:

if (sameVnode(oldVnode, vnode)) {
  patchVnode(oldVnode, vnode, insertedVnodeQueue);
} else {
  elm = oldVnode.elm as Node;
  parent = api.parentNode(elm);

  createElm(vnode, insertedVnodeQueue);

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

sameVnode如下定义:

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

sameVnode需要满足两个条件:

key的作用可以参考这里:cn.vuejs.org/v2/api/#key

新旧虚拟节点children的diff是整个虚拟dom算法的核心,首先解决以下几个特殊情况:

  • 新虚拟dom有children,旧虚拟dom没有children

处理方法:假如旧虚拟dom的text属性有定义,说明旧真实dom节点有且仅有文本子节点,需要先清除文本节点,然后将新虚拟节点children对应的真实节点添加到父节点。

// oldVnode  旧虚拟节点
// vnode 新虚拟节点
// oldCh 旧虚拟节点的子虚拟节点
// ch 新虚拟节点的子虚拟节点
// elm 新旧虚拟节点对应的真实节点
} else if (isDef(ch)) {
  if (isDef(oldVnode.text)) api.setTextContent(elm, '');
  addVnodes(elm, null, ch as Array<VNode>, 0, (ch as Array<VNode>).length - 1, insertedVnodeQueue);
}
  • 旧虚拟dom有children,新虚拟dom没有children

解决方法:删除掉旧虚拟节点children对应的真实节点即可

} else if (isDef(oldCh)) {
  removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
}
  • 旧虚拟节点text属性有定义,新虚拟节点text属性没定义且没有children

解决方法:说明旧节点有且仅有文本子节点,新节点为空节点,删除旧节点文本内容即可

api.setTextContent(elm, '');
  • 就虚拟节点的text属性有定义,新虚拟节点的text属性有定义

解决方法:说明新旧节点都有且仅有文本子节点,直接比较文本内容,不相同替换即可

} else if (oldVnode.text !== vnode.text) {
  api.setTextContent(elm, vnode.text as string);
}

以上是新旧虚拟dom子节点的四种特殊情况,还剩下一种普遍情况即:新旧虚拟dom均有children:

if (isDef(oldCh) && isDef(ch)) {
  if (oldCh !== ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue);
}

各种虚拟dom算法的差别在于updateChildren方法实现的不同,snabbdom算法的特点是给新旧children分别提供了头尾两个指针,diff过程中头尾指针均向中间靠拢,当任一children的头指针超过尾指针则diff过程结束。以下图这个例子做参照,相同字母代表两个虚拟dom是sameVnode:

img

具体的指针移动方式又可以分为以下6种情况:

  • 新children(下文记为ch)的头与旧children(下文记为oldCh)的头是sameVnode

解决方法:这种情况说明oldch头指针指向的虚拟dom的真实节点可原地复用,只需将oldch和ch的头指针分别向后移动一位即可,移动后如下:

img

解决方法:这种情况说明oldch尾指针指向的虚拟dom的真实节点可原地复用,只需将oldch和ch的尾指针分别向前移动一位即可,移动后如下:

img

解决方法:这种情况说明oldCh头指针指向的虚拟dom的真实节点仍然可以复用,但是其被移动到了oldCh尾指针指向虚拟dom的真实节点的后面,这时需要将oldCh的头指针向后移动一位,ch的尾指针向前移动一位,移动后如下:

img

解决方法:与上面相似,oldCh尾指针指向的虚拟dom的真实节点可以复用,但是其被移动到了oldCh头指针指向虚拟dom的真实节点的前面,这时需要将oldCh的尾指针向前移动一位,ch的头指针向后移动一位,移动后如下:

img

  • 在oldCh中可以找到与ch的头是sameVnode的虚拟节点(此节点记为moveVnode)

解决方法:这种情况意味着moveVnode对应的真实节点可以被复用,且移动到了oldCh头指针指向虚拟dom的真实节点的前面,此时需要将ch的头指针向后移动一位,同时将moveVnode设置为null,因为其已经被复用了,当头指针或者尾指针再指向它时需要跳过。移动后如下:

img

解决方法:当以上五种情况均不符合时,说明ch头指针指向的虚拟dom是一个全新的节点,也即在oldCh中不能找到可复用的节点,此时应当根据ch头指针指向的虚拟dom创建真实dom,并插入到oldCh头指针指向真实节点的前面。移动后如下:

img

以上分别对应了6种指针移动的方式,同时可以发现此时ch的头指针已经超越了尾指针,说明diff已经结束,但是此时oldCh的头指针依然小于尾指针,这说明在oldCh头指针和尾指针之间的虚拟dom对应的真实dom不能够被复用,需要删除掉。想象一下,假如oldCh的头指针超越了尾指针,而ch的头指针仍然小于尾指针,这说明了原有的dom节点全部可以复用,且ch的头指针和尾指针之间的虚拟dom代表了新的节点,需要被创建并插入到原有dom中。

下面是snabbdom中updateChildren的代码,添加了部分注释:

function updateChildren(parentElm: Node,
                        oldCh: Array<VNode>,
                        newCh: Array<VNode>,
                        insertedVnodeQueue: VNodeQueue) {
  let oldStartIdx = 0, newStartIdx = 0;
  let oldEndIdx = oldCh.length - 1;
  let oldStartVnode = oldCh[0];
  let oldEndVnode = oldCh[oldEndIdx];
  let newEndIdx = newCh.length - 1;
  let newStartVnode = newCh[0];
  let newEndVnode = newCh[newEndIdx];
  let oldKeyToIdx: any;
  let idxInOld: number;
  let elmToMove: VNode;
  let before: any;

  while (oldStartIdx <= oldEndIdx && newStartIdx <= newEndIdx) {
    // 下面4行代码我认为没有意义   不可能出现oldStartVnode或者oldEndVnode为null的情况
    if (oldStartVnode == null) {
      oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
    } else if (oldEndVnode == null) {
      oldEndVnode = oldCh[--oldEndIdx];
    // 已经被复用了   跳过
    } else if (newStartVnode == null) {
      newStartVnode = newCh[++newStartIdx];
    } else if (newEndVnode == null) {
      newEndVnode = newCh[--newEndIdx];
    //  对应上文第一种情况
    } else if (sameVnode(oldStartVnode, newStartVnode)) {
      patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
      oldStartVnode = oldCh[++oldStartIdx];
      newStartVnode = newCh[++newStartIdx];
    //  对应上文第二种情况
    } else if (sameVnode(oldEndVnode, newEndVnode)) {
      patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
      oldEndVnode = oldCh[--oldEndIdx];
      newEndVnode = newCh[--newEndIdx];
    // 对应上文第三种情况
    } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right
      patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
      api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
      oldStartVnode = oldCh[++oldStartIdx];
      newEndVnode = newCh[--newEndIdx];
    // 对应上文第四种情况
    } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left
      patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
      api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
      oldEndVnode = oldCh[--oldEndIdx];
      newStartVnode = newCh[++newStartIdx];
    } else {
      if (oldKeyToIdx === undefined) {
        oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
      }
      idxInOld = oldKeyToIdx[newStartVnode.key as string];
      // 新的虚拟节点
      if (isUndef(idxInOld)) { // New element
        api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
        newStartVnode = newCh[++newStartIdx];
      } else {
        elmToMove = oldCh[idxInOld];
        // key和sel均相同时才是sameVnode
        // 对应上文第五种情况
        if (elmToMove.sel !== newStartVnode.sel) {
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
        // 新的虚拟节点
        } else {
          patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
          oldCh[idxInOld] = undefined as any;
          api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node);
        }
        newStartVnode = newCh[++newStartIdx];
      }
    }
  }
  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);
    }
  }
}

至此,介绍了sanbbdom算法是如何进行diff的,全文完。

回到顶部