New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

snabbdom #11

Open
zyl1314 opened this Issue May 9, 2018 · 0 comments

Comments

Projects
None yet
1 participant
@zyl1314
Owner

zyl1314 commented May 9, 2018

前言

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相同

key的作用可以参考这里:https://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

  • ch的尾与oldCh的尾是sameVnode

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

img

  • oldCh的头与ch的尾是sameVnode

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

img

  • oldCh的尾与ch的头是sameVnode

解决方法:与上面相似,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的,全文完。

@zyl1314 zyl1314 closed this May 9, 2018

@zyl1314 zyl1314 reopened this May 9, 2018

@zyl1314 zyl1314 added the javascript label May 13, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment