VDOM算法笔记

vVirtal DOM主要包括以下三个方面

1. 使用 js 数据对象 表示 DOM 结构 -> VNode
2. 比较新旧两棵 虚拟 DOM 树的差异 -> diff
3. 将差异应用到真实的 DOM 树上 -> patch

snabbdom

snabbdom是一个优雅精简的vdom库，适合学习vdom思想和算法。下面的一切内容都是基于snabbdom.js的源码。

h函数

h 函数的主要功能是根据传入的参数，返回一个VNode对象。

根据snabbdom.js的h函数源码来分析： snabbdom中对h函数做了重载,这是ts的特性。使得h函数可以处理的情况更加清晰,分为以下四种:

1. 一个参数，选择器sel
2. 两个参数,选择器sel和数据data
3. 两个参数,选择器sel和子节点数组children
4. 三个参数,选择器，数据data，子节点数组children

根据下面的源码分析可以看出，除了这四种情况以外，对于SVG元素做了额外的处理，也就是添加了namespace。 最终都是调用vnode产生了一个VDOM节点。

/**
 * 重载h函数
 * 根据选择器 ，数据 ，创建 vnode
 */
export function h(sel: string): VNode;
export function h(sel: string, data: VNodeData): VNode;
export function h(sel: string, children: VNodeChildren): VNode;
export function h(sel: string, data: VNodeData, children: VNodeChildren): VNode;
/**
 *  h 函数比较简单，主要是提供一个方便的 工具 函数，方便创建 vnode 对象
 * @param sel 选择器
 * @param b    数据
 * @param c    子节点
 * @returns {{sel, data, children, text, elm}}
 */
export function h(sel: any, b?: any, c?: any): VNode {
  var data: VNodeData = {}, children: any, text: any, i: number;
  // 如果存在子节点
  // 三个参数的情况  sel , data , children | text
  if (c !== undefined) {
    // 那么h的第二项就是data
    data = b;
    // 如果c是数组，那么存在子element节点
    if (is.array(c)) { children = c; }
    //否则为子text节点
    else if (is.primitive(c)) { text = c; }
    // 说明c是一个子元素
    else if (c && c.sel) { children = [c]; }
    //如果c不存在，只存在b，那么说明需要渲染的vdom不存在data部分，只存在子节点部分
  } else if (b !== undefined) {
    // 两个参数的情况 : sel , children | text
    // 两个参数的情况 : sel , data
    // 子元素数组
    if (is.array(b)) { children = b; }
    //子元素文本节点
    else if (is.primitive(b)) { text = b; }
    // 单个子元素
    else if (b && b.sel) { children = [b]; }
    // 不是元素，而是数据
    else { data = b; }
  }
  //  对文本或者数字类型的子节点进行转化
  if (children !== undefined) {
    for (i = 0; i < children.length; ++i) {
       // 如果children是文本或数字 ，则创建文本节点
  //{sel: sel, data: data, children: children, text: text, elm: elm, key: key};
  //文本节点sel和data属性都是undefined
      if (is.primitive(children[i])) children[i] = vnode(undefined, undefined, undefined, children[i], undefined);
    }
  }
  //  针对svg的node进行特别的处理
  if (
    sel[0] === 's' && sel[1] === 'v' && sel[2] === 'g' &&
    (sel.length === 3 || sel[3] === '.' || sel[3] === '#')
  ) {
      // 增加 namespace
    addNS(data, children, sel);
  }
  // 返回一个正常的vnode对象
  return vnode(sel, data, children, text, undefined);
};
export default h;
复制代码

vnode函数

vnode函数 非常简单。仅仅是根据输入参数返回了一个VNode类型的对象

// 根据传入的 属性 ，返回一个 vnode 对象
export function vnode(
    sel: string | undefined,
    data: any | undefined,
    children: Array<VNode | string> | undefined,
    text: string | undefined,
    elm: Element | Text | undefined
): VNode {
    let key = data === undefined ? undefined : data.key;
    return {
        sel: sel,
        data: data,
        children: children,
        text: text,
        elm: elm,
        key: key
    };
}
export default vnode;
复制代码

下面是VNode的源码：

/**
 * 定义VNode类型
 */
export interface VNode {
    // 选择器
    sel: string | undefined;
    // 数据，主要包括属性、样式、数据、绑定时间等
    data: VNodeData | undefined;
    // 子节点
    children: Array<VNode | string> | undefined;
    // 关联的原生节点
    elm: Node | undefined;
    // 文本
    text: string | undefined;
    // key , 唯一值，为了优化性能
    key: Key | undefined;
}
复制代码

另外还有一个比较重要的类型VNodeData.

/**
 * VNodeData节点全部都是可选属性，也可动态添加任意类型的属性
 */
export interface VNodeData {
  // vnode上的其他属性
   // 属性 能直访问和接用  
  props?: Props;
  // vnode上面的浏览器原生属性，可以使用setAttribute设置的
  attrs?: Attrs;
  //样式类,class属性集合
  class?: Classes;
  // style属性集合
  style?: VNodeStyle;
  // vnode上面挂载的数据集合
  dataset?: Dataset;
  // 监听事件集合
  on?: On;
  // 
  hero?: Hero;
  // 额外附加的数据
  attachData?: AttachData;
  // 钩子函数集合，执行到不同的阶段调用不同的钩子函数
  hook?: Hooks;
  //
  key?: Key;
  // 命名空间 SVGs 命名空间，主要用于SVG
  ns?: string; // for SVGs
  fn?: () => VNode; // for thunks
  args?: Array<any>; // for thunks
  //其它额外的属性
  [key: string]: any; // for any other 3rd party module
}
复制代码

正式开始

一切的一切都要从这个snabbdom.ts中的这个init方法开始。

Virtual Dom 树对比的策略

1. 同级对比

按照层序的方式遍历比较

对比的时候，只针对同级的严肃进行对比，减少算法复杂度。

2. 就近复用

为了尽可能不发生 DOM 的移动，会就近复用相同的 DOM 节点，复用的依据是判断是否是同类型的 dom 元素

/**
 * 
 * @param modules 
 * @param domApi 
 * @returns 返回 patch 方法
 */
export function init(modules: Array<Partial<Module>>, domApi?: DOMAPI) {
  let i: number, j: number, cbs = ({} as ModuleHooks);

  const api: DOMAPI = domApi !== undefined ? domApi : htmlDomApi;
  // 循环 hooks , 将每个 modules 下的 hook 方法提取出来存到 cbs 里面
 // 返回结果 eg ： cbs['create'] = [modules[0]['create'],modules[1]['create'],...];
  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) {
    ...
  }
  // 创建一个删除的回调，多次调用这个回调，直到监听器都没了，就删除元素
  function createRmCb(childElm: Node, listeners: number) {
    ...
  }

  // 将 vnode 转换成真正的 DOM 元素
  function createElm(vnode: VNode, insertedVnodeQueue: VNodeQueue): Node {
    ...
  }

  // 添加 Vnodes 到 真实 DOM 中
  function addVnodes(parentElm: Node,
                     before: Node | null,
                     vnodes: Array<VNode>,
                     startIdx: number,
                     endIdx: number,
                     insertedVnodeQueue: VNodeQueue) {
    ...
  }

  function invokeDestroyHook(vnode: VNode) {
    let i: any, j: number, data = vnode.data;
    ...
  }

  function removeVnodes(parentElm: Node,
                        vnodes: Array<VNode>,
                        startIdx: number,
                        endIdx: number): void {
    ...
  }
  
  function updateChildren(parentElm: Node,
                          oldCh: Array<VNode>,
                          newCh: Array<VNode>,
                          insertedVnodeQueue: VNodeQueue) {
  ...省略函数
  }

  function patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) {
   ...省略函数体
  }
  // 返回patch 方法
  /**
   * 触发 pre 钩子
   *  如果老节点非 vnode， 则新创建空的 vnode
   *  新旧节点为 sameVnode 的话，则调用 patchVnode 更新 vnode , 否则创建新节点
   *  触发收集到的新元素 insert 钩子
   *  触发 post 钩子
   * @param oldVnode 
   * @param vnode 
   * @returns  vnode
   */
  function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    //收集新插入到的元素
    const insertedVnodeQueue: VNodeQueue = [];
    //先调用pre回调
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();

    // 如果老节点非 vnode ， 则创建一个空的 vnode
    if (!isVnode(oldVnode)) {
      oldVnode = emptyNodeAt(oldVnode);
    }
    //  如果是同个节点，则进行修补
    if (sameVnode(oldVnode, vnode)) {
      // 进入patch流程
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      // 不同 Vnode 节点则新建
      // as 是告诉类型检查器，次数oldVnode.elm的类型应该是Node类型
      elm = oldVnode.elm as Node;
      //取到父节点node.parentNode属性
      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);
      }
    }
    // 遍历所有收集到的插入节点，调用插入的钩子，
    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      (((insertedVnodeQueue[i].data as VNodeData).hook as Hooks).insert as any)(insertedVnodeQueue[i]);
    }
    // 调用post的钩子
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
  return patch;
}
复制代码

从上面的代码里看init方法除了提取了create钩子以外就是声明了几个重要的函数，并且返回了一个函数 patch。

patch

patch函数只接受两个参数， patch(oldVnode: VNode | Element, vnode: VNode) ,第一个参数oldNode可以使VNode或者Element类型，第二个参数为VNode类型。

声明了一个insertedVnodeQueue，用来收集需要插入的元素队列。 步骤如下:

1. 如果oldVnode不是VNode类型，那么调用emptyNodeAt创建一个空的VNode

2. 如果oldNode和vnode是同一个节点，那么直接进入patchVNode流程 patchVNode流程后面再详细介绍

3. 如果 不是同一个节点则先获取oldVnode.elm的父DOM元素。将新元素插入到oldVnode.elm的下一个兄弟节点之前，然后移除oldVnode。其效果等同于使用新创建的元素替换了旧元素。

4. 遍历insertedVnodeQueue队列，调用insert钩子

5. 调用post钩子

6. 返回vnode节点.

patchVnode

接下来的重点在于patchVnode。 前面定义的VNode结构类型，中包含了children和text两个字段，这是为了将元素子节点和文本分开处理

patchVnode函数只接受三个参数， patchVnode(oldVnode: VNode, vnode: VNode, insertedVnodeQueue: VNodeQueue) , 第一个参数oldNode是VNode类型， 第二个参数为VNode类型。 第三个参数是插入的VNode队列

patchVnode的主要逻辑如下:

1. 调用oldNode和vnode的prepatch钩子
2. 如果oldNode和vnode引用的地址相同，说明是同一个对象，直接返回
3. 如果vnode.text属性为undefined，说明子节点是元素，假设旧的子节点元素用oldCh表示，新的子元素节点用ch表示，此时存在四种情况:

updateChildren

4. 如果vnode.text属性不是undefined，说明新节点是文本节点，此时如果oldNode是元素节点，此时应该移除所有元素，然后设置文本内容
5. 处理完毕，触发post钩子函数

updateChildren

上文中关键的地方在于 updateChildren ，这个过程处理新旧子元素数组的对比。 这里就是diff算法的核心逻辑了。其实也很简单。逻辑如下:

1. 有线处理特殊场景，先对比两端，也就是

- (1)旧 vnode 头 vs 新 vnode 头（顺序）
- (2)旧 vnode 尾 vs 新 vnode 尾（顺序）
- (3)旧 vnode 头 vs 新 vnode 尾（倒序）
- (4)旧 vnode 尾 vs 新 vnode 头（倒序）
复制代码

1. 首尾不一样的情况，寻找 key 相同的节点，找不到则新建元素
2. 如果找到 key，但是，元素选择器变化了，也新建元素
3. 如果找到 key，并且元素选择没变， 则移动元素
4. 两个列表对比完之后，清理多余的元素，新增添加的元素

后面的源码因为太长了就不贴了，有兴趣的话就看 这里 ,欢迎大家批评指正。