关于Virtual Dom的那些事(五)

前言

上一篇《关于Virtual Dom的那些事(四)》主要是介绍了Thunk概念,加上之前所有有的内容都只是snabbbom的前菜,本篇直接分析其200 SLOC(Source Lines of Code),大概200行的核心代码。并附上其它剩余所有代码的源码分析。

200 SLOC(Source Lines of Code)

  /******************* 下面是核心diff算法 ********************/
  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) {
      if (oldStartVnode == null) { // 旧最左边vnode为null,下标右移一位
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
      } else if (oldEndVnode == null) { // 旧最右边vnode为null,下标左移一位
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) { // 新最左边vnode为null,下标右移一位
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) { // 新最右边vnode为null,下标左移一位
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // 旧最左边vnode等于新最左边vnode,执行patchVnode,大家下标一起右移一位
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 旧最右边vnode等于新最右边vnode,执行patchVnode,大家下标一起左移一位
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right,旧最左边vnode等于新最右边vnode,执行patchVnode,旧节点要移到最右边
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
        oldStartVnode = oldCh[++oldStartIdx]; // 旧最左边vnode下标右移一位
        newEndVnode = newCh[--newEndIdx]; // 新最右边vnode下标左移一位
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left,旧最右边vnode等于新最左边vnode,执行patchVnode,旧节点要移到最左边
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
        oldEndVnode = oldCh[--oldEndIdx]; // 旧最右边vnode下标左移一位
        newStartVnode = newCh[++newStartIdx]; // 新最左边vnode下标右移一位
      } else { // 上面匹配不上
        if (oldKeyToIdx === undefined) { // key优化处理。如果是vue开发时,有添加key时,节点会被优化处理
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) { // New element或者没有key被当作新节点处理,直接插入
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          newStartVnode = newCh[++newStartIdx];
        } else { // 非新节点,但被移到了中间,需要移动
          elmToMove = oldCh[idxInOld];
          if (elmToMove.sel !== newStartVnode.sel) { // 如果key节相等,但选择器变了,直接插入
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          } else { // key相等且选择器也相等
            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) { // 如果旧vnode的下标到尽头或者新vnode的下标到尽头
      if (oldStartIdx > oldEndIdx) { // 如果旧vnode的下标到尽头
        before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue); // 把剩余的节点全部插入
      } else { // 如果新vnode的下标到尽头
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); // 删除剩余的所有旧的节点
      }
    }
  }

diff算法基本思路

如上图所示,新旧childrens’ vnodes进行比较来进行vnode patch,主要是参照节点选择器是否相等作为标准。

diff的策略

diff的策略
diff的策略

完整的snabbdom diff && patch源码分析

/* global module, document, Node */
import {Module} from './modules/module';
import {Hooks} from './hooks';
import vnode, {VNode, VNodeData, Key} from './vnode';
import * as is from './is';
import htmlDomApi, {DOMAPI} from './htmldomapi';

function isUndef(s: any): boolean { return s === undefined; } // 是否未定义
function isDef(s: any): boolean { return s !== undefined; } // 是否已定义

type VNodeQueue = Array<VNode>; // vnode队列

const emptyNode = vnode('', {}, [], undefined, undefined); // 生成一个空的vnode

// 是否为同一个vnode
function sameVnode(vnode1: VNode, vnode2: VNode): boolean {
  return vnode1.key === vnode2.key && vnode1.sel === vnode2.sel;
}

// 是否为vnode
function isVnode(vnode: any): vnode is VNode {
  return vnode.sel !== undefined;
}

// 创建使用string类型的key来表示数组的index的对象
type KeyToIndexMap = {[key: string]: number};

type ArraysOf<T> = { // 对象内所有的key对应的值组成数组入栈
  [K in keyof T]: (T[K])[];
}
/* export interface Module {
  pre: PreHook;
  create: CreateHook;
  update: UpdateHook;
  destroy: DestroyHook;
  remove: RemoveHook;
  post: PostHook;
} */
type ModuleHooks = ArraysOf<Module>;  // module内所有的key对应的回调勾子函数组成数组入栈

// 把特定下标的children数组转为KeyToIndexMap格式
function createKeyToOldIdx(children: Array<VNode>, beginIdx: number, endIdx: number): KeyToIndexMap {
  let i: number, map: KeyToIndexMap = {}, key: Key | undefined, ch;
  for (i = beginIdx; i <= endIdx; ++i) {
    ch = children[i];
    if (ch != null) {
      key = ch.key;
      if (key !== undefined) map[key] = i;
    }
  }
  return map;
}

const hooks: (keyof Module)[] = ['create', 'update', 'remove', 'destroy', 'pre', 'post'];

export {h} from './h';
export {thunk} from './thunk';

// Partial的作用是所有的属性,要么不赋值,要么按照module规定赋值.
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) { // 支持自定义的DOMAPI,如果你不想用snabbdom内置的htmlDomApi,可以自己重写一个
  // cbs 用于收集 module 中的 hook
  let i: number, j: number, cbs = ({} as ModuleHooks);

  const api: DOMAPI = domApi !== undefined ? domApi : htmlDomApi;
  // 收集 module 中的 hook
  for (i = 0; i < hooks.length; ++i) {
    cbs[hooks[i]] = [];
    for (j = 0; j < modules.length; ++j) {
      const hook = modules[j][hooks[i]];
      if (hook !== undefined) {
        (cbs[hooks[i]] as Array<any>).push(hook);
      }
    }
  }

  function emptyNodeAt(elm: Element) { // 转换成空的vnode
    const id = elm.id ? '#' + elm.id : '';
    const c = elm.className ? '.' + elm.className.split(' ').join('.') : '';
    return vnode(api.tagName(elm).toLowerCase() + id + c, {}, [], undefined, elm);
  }

  function createRmCb(childElm: Node, listeners: number) { // 删除vnode后执行回调去真正操作删除Dom
    return function rmCb() {
      if (--listeners === 0) {
        const parent = api.parentNode(childElm);
        api.removeChild(parent, childElm);
      }
    };
  }

  // 创建真正的 dom 节点
  function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue): Node {
    let i: any, data = vnode.data;
    // 调用元素的 init hook
    if (data !== undefined) {
      if (isDef(i = data.hook) && isDef(i = i.init)) {
        i(vnode);
        data = vnode.data;
      }
    }
    let children = vnode.children, sel = vnode.sel;
    // 注释节点
    if (sel === '!') {
      if (isUndef(vnode.text)) {
        vnode.text = '';
      }
      // 创建注释节点
      vnode.elm = api.createComment(vnode.text as string);
    } else if (sel !== undefined) {
      // Parse selector
      const hashIdx = sel.indexOf('#');
      const dotIdx = sel.indexOf('.', hashIdx);
      const hash = hashIdx > 0 ? hashIdx : sel.length;
      const dot = dotIdx > 0 ? dotIdx : sel.length;
      const tag = hashIdx !== -1 || dotIdx !== -1 ? sel.slice(0, Math.min(hash, dot)) : sel;
      const elm = vnode.elm = isDef(data) && isDef(i = (data as VNodeData).ns) ? api.createElementNS(i, tag)
                                                                               : api.createElement(tag);
      if (hash < dot) elm.setAttribute('id', sel.slice(hash + 1, dot)); if (dotIdx > 0) elm.setAttribute('class', sel.slice(dot + 1).replace(/\./g, ' '));
      // 调用 module 中的 create hook
      for (i = 0; i < cbs.create.length; ++i) cbs.create[i](emptyNode, vnode);
      // 挂载子节点
      if (is.array(children)) {
        for (i = 0; i < children.length; ++i) {
          const ch = children[i];
          if (ch != null) {
            api.appendChild(elm, createElm(ch as VNode, insertedVnodeQueue));
          }
        }
      } else if (is.primitive(vnode.text)) {
        api.appendChild(elm, api.createTextNode(vnode.text));
      }
      i = (vnode.data as VNodeData).hook; // Reuse variable
      // 调用 vnode 上的 hook
      if (isDef(i)) {
        // 调用 create hook
        if (i.create) i.create(emptyNode, vnode);
        // insert hook 存储起来 等 dom 插入后才会调用,这里用个数组来保存能避免调用时再次对 vnode 树做遍历
        if (i.insert) insertedVnodeQueue.push(vnode);
      }
    } else {
      // 文本节点
      vnode.elm = api.createTextNode(vnode.text as string);
    }
    return vnode.elm;
  }

  function addVnodes(parentElm: Node,
                     before: Node | null,
                     vnodes: Array<VNode>,
                     startIdx: number,
                     endIdx: number,
                     insertedVnodeQueue: VNodeQueue) {
    for (; startIdx <= endIdx; ++startIdx) {
      const ch = vnodes[startIdx];
      if (ch != null) {
        api.insertBefore(parentElm, createElm(ch, insertedVnodeQueue), before); // 用insertBefore可以便于定好before来向前按顺序插入
      }
    }
  }

  function invokeDestroyHook(vnode: VNode) { // 调用有定义的所有的destroy hook
    let i: any, j: number, data = vnode.data;
    if (data !== undefined) {
      if (isDef(i = data.hook) && isDef(i = i.destroy)) i(vnode);
      for (i = 0; i < cbs.destroy.length; ++i) cbs.destroy[i](vnode);
      if (vnode.children !== undefined) {
        for (j = 0; j < vnode.children.length; ++j) {
          i = vnode.children[j];
          if (i != null && typeof i !== "string") {
            invokeDestroyHook(i);
          }
        }
      }
    }
  }

  function removeVnodes(parentElm: Node,
                        vnodes: Array<VNode>,
                        startIdx: number,
                        endIdx: number): void {
    for (; startIdx <= endIdx; ++startIdx) { let i: any, listeners: number, rm: () => void, ch = vnodes[startIdx];
      if (ch != null) {
        if (isDef(ch.sel)) {
          invokeDestroyHook(ch);
          listeners = cbs.remove.length + 1;
          rm = createRmCb(ch.elm as Node, listeners); // 创建删除函数
          for (i = 0; i < cbs.remove.length; ++i) cbs.remove[i](ch, rm);
          if (isDef(i = ch.data) && isDef(i = i.hook) && isDef(i = i.remove)) {
            i(ch, rm); // 如果有remove hook就先执行hook再执行删除
          } else {
            rm(); // 执行删除操作
          }
        } else { // Text node
          api.removeChild(parentElm, ch.elm as Node);
        }
      }
    }
  }

  /******************* 下面是核心diff算法 ********************/
  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) {
      if (oldStartVnode == null) { // 旧最左边vnode为null,下标右移一位
        oldStartVnode = oldCh[++oldStartIdx]; // Vnode might have been moved left
      } else if (oldEndVnode == null) { // 旧最右边vnode为null,下标左移一位
        oldEndVnode = oldCh[--oldEndIdx];
      } else if (newStartVnode == null) { // 新最左边vnode为null,下标右移一位
        newStartVnode = newCh[++newStartIdx];
      } else if (newEndVnode == null) { // 新最右边vnode为null,下标左移一位
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newStartVnode)) { // 旧最左边vnode等于新最左边vnode,执行patchVnode,大家下标一起右移一位
        patchVnode(oldStartVnode, newStartVnode, insertedVnodeQueue);
        oldStartVnode = oldCh[++oldStartIdx];
        newStartVnode = newCh[++newStartIdx];
      } else if (sameVnode(oldEndVnode, newEndVnode)) { // 旧最右边vnode等于新最右边vnode,执行patchVnode,大家下标一起左移一位
        patchVnode(oldEndVnode, newEndVnode, insertedVnodeQueue);
        oldEndVnode = oldCh[--oldEndIdx];
        newEndVnode = newCh[--newEndIdx];
      } else if (sameVnode(oldStartVnode, newEndVnode)) { // Vnode moved right,旧最左边vnode等于新最右边vnode,执行patchVnode,旧节点要移到最右边
        patchVnode(oldStartVnode, newEndVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldStartVnode.elm as Node, api.nextSibling(oldEndVnode.elm as Node));
        oldStartVnode = oldCh[++oldStartIdx]; // 旧最左边vnode下标右移一位
        newEndVnode = newCh[--newEndIdx]; // 新最右边vnode下标左移一位
      } else if (sameVnode(oldEndVnode, newStartVnode)) { // Vnode moved left,旧最右边vnode等于新最左边vnode,执行patchVnode,旧节点要移到最左边
        patchVnode(oldEndVnode, newStartVnode, insertedVnodeQueue);
        api.insertBefore(parentElm, oldEndVnode.elm as Node, oldStartVnode.elm as Node);
        oldEndVnode = oldCh[--oldEndIdx]; // 旧最右边vnode下标左移一位
        newStartVnode = newCh[++newStartIdx]; // 新最左边vnode下标右移一位
      } else { // 上面匹配不上,进行key判断
        if (oldKeyToIdx === undefined) { // key优化处理。如果是vue开发时,有添加key时,节点会被优化处理
          oldKeyToIdx = createKeyToOldIdx(oldCh, oldStartIdx, oldEndIdx);
        }
        idxInOld = oldKeyToIdx[newStartVnode.key as string];
        if (isUndef(idxInOld)) { // New element或者没有key被当作新节点处理,直接插入,新最左边的vnode下标右移一位
          api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          newStartVnode = newCh[++newStartIdx];
        } else { // 非新节点,但被移到了中间,需要移动
          elmToMove = oldCh[idxInOld];
          if (elmToMove.sel !== newStartVnode.sel) { // 如果key相等,但选择器变了,直接插入
            api.insertBefore(parentElm, createElm(newStartVnode, insertedVnodeQueue), oldStartVnode.elm as Node);
          } else { // key相等且选择器也相等
            patchVnode(elmToMove, newStartVnode, insertedVnodeQueue);
            oldCh[idxInOld] = undefined as any; // 删除了旧的节点
            api.insertBefore(parentElm, (elmToMove.elm as Node), oldStartVnode.elm as Node); // 把旧节点插入到新的位置
          }
          newStartVnode = newCh[++newStartIdx]; // 新最左边的vnode下标右移一位
        }
      }
    }
    if (oldStartIdx <= oldEndIdx || newStartIdx <= newEndIdx) { // 如果旧vnode的下标到尽头或者新vnode的下标到了尽头 if (oldStartIdx > oldEndIdx) { // 如果旧vnode的下标到了尽头
        before = newCh[newEndIdx+1] == null ? null : newCh[newEndIdx+1].elm;
        addVnodes(parentElm, before, newCh, newStartIdx, newEndIdx, insertedVnodeQueue); // 把剩余的节点全部插入
      } else { // 如果新vnode的下标到尽头
        removeVnodes(parentElm, oldCh, oldStartIdx, oldEndIdx); // 删除剩余的所有旧的节点
      }
    }
  }

  function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
    let i: any, hook: any;
    // 调用 prepatch hook
    if (isDef(i = vnode.data) && isDef(hook = i.hook) && isDef(i = hook.prepatch)) {
      i(oldVnode, vnode);
    }
    const elm = vnode.elm = (oldVnode.elm as Node);
    let oldCh = oldVnode.children;
    let ch = vnode.children;
    if (oldVnode === vnode) return;
    if (vnode.data !== undefined) {
      // 调用 module 上的 update hook
      for (i = 0; i < cbs.update.length; ++i) cbs.update[i](oldVnode, vnode);
      i = vnode.data.hook;
      // 调用 vnode 上的 update hook
      if (isDef(i) && isDef(i = i.update)) i(oldVnode, vnode);
    }
    if (isUndef(vnode.text)) {
      if (isDef(oldCh) && isDef(ch)) {
        // 新旧节点均存在 children,且不一样时,对 children 进行 diff
        // thunk 中会做相关优化和这个相关
        if (oldCh !== ch) updateChildren(elm, oldCh as Array<VNode>, ch as Array<VNode>, insertedVnodeQueue);
      } else if (isDef(ch)) {
        // 旧节点不存在 children 新节点有 children
        // 旧节点存在 text 置空
        if (isDef(oldVnode.text)) api.setTextContent(elm, '');
        // 加入新的 vnode
        addVnodes(elm, null, ch as Array<VNode>, 0, (ch as Array<VNode>).length - 1, insertedVnodeQueue);
      } else if (isDef(oldCh)) {
        // 新节点不存在 children 旧节点存在 children 移除旧节点的 children
        removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
      } else if (isDef(oldVnode.text)) {
        // 旧节点存在 text 置空
        api.setTextContent(elm, '');
      }
    } else if (oldVnode.text !== vnode.text) {
      // 更新 text
      if (isDef(oldCh)) {
        removeVnodes(elm, oldCh as Array<VNode>, 0, (oldCh as Array<VNode>).length - 1);
      }
      api.setTextContent(elm, vnode.text as string);
    }
    // 调用 postpatch hook
    if (isDef(hook) && isDef(i = hook.postpatch)) {
      i(oldVnode, vnode);
    }
  }

  return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    
    // 调用 module 中的 pre hook
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i](); 
    // 如果传入的是 Element 转成空的 vnode
    if (!isVnode(oldVnode)) {
      oldVnode = emptyNodeAt(oldVnode);
    }
    // sameVnode 时 (sel 和 key相同) 调用 patchVnode
    if (sameVnode(oldVnode, vnode)) {
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      elm = oldVnode.elm as Node;
      parent = api.parentNode(elm);
      // 创建新的 dom 节点 vnode.elm
      createElm(vnode, insertedVnodeQueue);

      if (parent !== null) {
        // 插入 dom
        api.insertBefore(parent, vnode.elm as Node, api.nextSibling(elm));
        // 移除旧 dom
        removeVnodes(parent, [oldVnode], 0, 0);
      }
    }
    // 调用元素上的 insert hook,注意 insert hook 在 module 上不支持
    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      (((insertedVnodeQueue[i].data as VNodeData).hook as Hooks).insert as any)(insertedVnodeQueue[i]);
    }
     // 调用 module post hook
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
}

至此,关于Virtual Dom的那些事系列全部完成,了解更多可直接关注snabbdom官方github源码

作者: 博主

Talk is cheap, show me the code!

发表评论

电子邮件地址不会被公开。

Captcha Code