Diff算法 // RocketTurtle

diff算法

diff算法是发生在虚拟dom上的
新虚拟dom和旧虚拟dom进行diff（精细化比较），算出如何最小量更新，最后反映到真实的dom上


import {
  init,
  classModule,
  propsModule,
  styleModule,
  eventListenersModule,
  h,
} from "snabbdom";

const patch = init([
  // Init patch function with chosen modules
  classModule, // makes it easy to toggle classes
  propsModule, // for setting properties on DOM elements
  styleModule, // handles styling on elements with support for animations
  eventListenersModule, // attaches event listeners
]);

const container = document.getElementById("container");

const myVnode = h('ul', {
  class: {
    'box': true
  }
}, [
  h('li', '技'),
  h('li', '术'),
  h('li', '博'),
  h('li', '客'),
  h('a', {
    props: {
      href: 'https://rocketturtlewqt.github.io'
    }
  }, '地址')
]);

patch(container, myVnode);

h函数嵌套

diff算法底层调用了patch，patch的作用就是让虚拟节点上树
h函数的作用就是用来生成虚拟dom，h函数可以嵌套

虚拟dom结构

children：子节点
data：当前标签的属性
elm：挂载的节点，是否上树
key：节点的唯一标识
sel：选择器，当前标签名
text：标签内的文本节点

diff算法特点

最小量更新，key是虚拟节点的唯一标识（diff算法会根据key值去找缓存中相对应的虚拟节点进行缓存复用），若没有key值，则按顺序进行复用。
只有是同一个虚拟节点才会进行精细化比较。
diff算法是同层比较，不会跨层比较，同层虚拟节点的顺序可以打乱，不影响diff算法缓存复用。

patch算法

return function patch(oldVnode: VNode | Element, vnode: VNode): VNode {
    let i: number, elm: Node, parent: Node;
    const insertedVnodeQueue: VNodeQueue = [];
    for (i = 0; i < cbs.pre.length; ++i) cbs.pre[i]();
    /**
     * 判断旧的节点是不是虚拟节点
     */
    if (!isVnode(oldVnode)) {
      /**
       * 如果旧节点不是虚拟节点，就将其包装成虚拟节点
       */
      oldVnode = emptyNodeAt(oldVnode);

    }
    /**
     * 判断新旧节点是不是同一个虚拟节点
     */
    if (sameVnode(oldVnode, vnode)) {
      /**
       * 如果新旧节点是同一个虚拟节点，就对它们进行精细化比较
       */
      patchVnode(oldVnode, vnode, insertedVnodeQueue);
    } else {
      /**
       * 如果新旧节点不是同一个虚拟节点，就移除旧节点，添加新节点
       */
      elm = oldVnode.elm!;
      parent = api.parentNode(elm) as Node;

      createElm(vnode, insertedVnodeQueue);

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

    for (i = 0; i < insertedVnodeQueue.length; ++i) {
      insertedVnodeQueue[i].data!.hook!.insert!(insertedVnodeQueue[i]);
    }
    for (i = 0; i < cbs.post.length; ++i) cbs.post[i]();
    return vnode;
  };
}

patch算法流程图

diff算法流程图

diff算法流程图

自我实现的diff算法

vnode

vnode函数用来生成虚拟dom，虚拟dom本质上就是一个js对象

/**
 * 虚拟dom就是一个js对象
 */
export default function Vnode(sel, data, children, text, elm, key) {
  return {
    sel,
    data,
    children,
    text,
    elm,
    key
  }
}

h函数

用来生成虚拟dom
主要针对以下三种情况

h(‘li’,{},‘a’)：虚拟节点无子虚拟节点，只有内部文本
h(‘li’,{},[])：虚拟节点有多个子虚拟节点
h(‘li’,{},h())：虚拟节点只有一个虚拟节点

import vnode from './vnode';

/**
 * 自我手写的简易版h渲染函数，目前只支持如下三种情况（必须接收三个参数）
 * 1.h('li',{},'a')
 * 2.h('li',{},[])
 * 3.h('li',{},h())
 */
export default function (sel, data, c) {
  const elm = document.createElement(sel);
  if (typeof c === 'string' || typeof c === 'number') {
    elm.innerText = c;
    return vnode(sel, data, undefined, c, elm, data['key']);
  } else if (Array.isArray(c)) {
    let children = [];
    for (let i = 0; i < c.length; i++){
      if (!(typeof c[i] === 'object' && c[i].hasOwnProperty('sel'))) {
        throw new Error('这是一个低配版本的渲染函数，只支持接收固定三个参数');
      }
      children.push(c[i]);
      elm.appendChild(c[i].elm);
    }
    return vnode(sel, data, children, undefined, elm, data['key']);
  } else if (typeof c === 'object' && c.hasOwnProperty('sel')) {
    let children = [c];
    elm.appendChild(c.elm);
    return vnode(sel, data, children, undefined, elm, data['key']);
  } else {
    throw new Error('这是一个低配版本的渲染函数，只支持接收固定三个参数');
  }
}

createElement

函数的作用就是根据虚拟dom来创建真身dom元素

export default function createElement(vnode) {
  const newDom = document.createElement(vnode.sel);
  if (vnode.text !== '' && (vnode.children == undefined || vnode.children.length === 0)) {
    newDom.innerText = vnode.text;
  } else if (Array.isArray(vnode.children) && vnode.children.length > 0) {
    for (let i = 0; i < vnode.children.length; i++){
      newDom.appendChild(createElement(vnode.children[i]));
    }
  }
  vnode.elm = newDom;
  return newDom;
}

patch函数

patch函数主要用来将虚拟dom转为真实dom上树用的

假若新旧节点不是同一个虚拟节点，就先根据新虚拟节点去创建真实dom节点，插在旧虚拟节点对应的那个真实dom节点的前面，然后将旧虚拟节点对应的那个真实dom节点移除。
假若新旧节点是同一个虚拟节点，就去调用patchVnode函数就行精细化比较

import vnode from './vnode';
import createElement from './createElement';
import patchVnode from './patchVnode';
/**
 * patch函数用来将虚拟dom转换为真实dom上树
 */
export default function (oldVnode, newVnode) {
  if (oldVnode.sel === '' || oldVnode.sel == undefined) {
    oldVnode = vnode(oldVnode.tagName.toLowerCase(), {}, [], oldVnode.innerText, oldVnode, undefined);
  }

  if (newVnode.key === oldVnode.key && newVnode.sel === oldVnode.sel) {
    patchVnode(newVnode, oldVnode);
  } else {
    //新旧节点不是同一个虚拟节点
    const newDom = createElement(newVnode);
    oldVnode.elm.parentNode.insertBefore(newDom, oldVnode.elm);
    oldVnode.elm.parentNode.removeChild(oldVnode.elm);
  }
}

patchVnode函数

patchVnode函数主要在新旧两个节点是同一种类型的对象情况下进行精细化比较

新旧虚拟节点对应的引用相同：什么都不做
新旧虚拟节点的text属性：text属性相同，什么也不做；不同，就把旧的替换为新的。
新旧节点是否有孩子的情况：旧没有，新有，清空旧的text，将新虚拟节点的子虚拟节点转换为真实dom挂在到旧虚拟节点对应的真实节点下;若新旧都有子虚拟节点的情况下，就去调用updateChildren函数进行更精细化的比较

import createElement from './createElement';
import updateChildren from './updateChildren';
/**
 * patchVnode函数用来处理，新旧虚拟dom是同一个虚拟节点的情况
 */
export default function patchVnode(newVnode, oldVnode) {
  if (oldVnode === newVnode) return;
  if (newVnode.text !== '' && (newVnode.children === undefined || newVnode.children.length === 0)) {
    if (newVnode.text === oldVnode.text) return;
    else {
      oldVnode.elm.innerText = newVnode.text;
      oldVnode.text = newVnode.text;
    }
  } else {
    //进行精细化比较
    if (oldVnode.children !== undefined && oldVnode.children.length > 0) {
      updateChildren(oldVnode.elm, oldVnode.children, newVnode.children);
    } else {
      oldVnode.elm.innerText = '';
      for (let i = 0; i < newVnode.children.length; i++){
        oldVnode.elm.appendChild(createElement(newVnode.children[i]));
      }
    }
    // console.log(oldVnode);
  }
}

updateChildren函数

updateChildren是diff算法对新旧虚拟dom比对的一个优化策略
该算法的核心就是四个指针，新前、旧前、新后、旧后

四个指针

当新前命中旧前，就将两个指针往下移动一个单位。
当新后命中旧后，就将两个指针向上移动一个单位。
当新后命中旧前，将新后指向的节点移动到旧后的的后面。
当新前命中旧后，将新前指向的节点移动到旧前的前面。
当前面四种情况都没命中，就去暴力比对新前和旧前与旧后之间的节点是否有命中的，将命中的节点记为X，将X赋为undefined，将新前节点移到旧前的前面。

当新前>新后或旧前>旧后，那么就去判断哪两个指针之间还有剩余节点

当新前与新后之间有剩余节点，就将它们放在旧前的前面
当旧前与旧后之间有剩余节点，就说明这些节点是将要被删除的节点，将它们全部删除

import createElement from './createElement';
import patchVnode from './patchVnode';

function judge(oldVnode, newVnode) {
  return oldVnode.sel === newVnode.sel && oldVnode.key === newVnode.key;
}
/**
 * updateChildren函数用来处理新旧虚拟节点是同一个节点，并且都有children属性的情况
 */
export default function updateChildren(parentElm, oldCh, newCh) {
  let newStartIdx = 0;
  let oldStartIdx = 0;
  let newEndIdx = newCh.length - 1;
  let oldEndIdx = oldCh.length - 1;
  let mp;

  while (newStartIdx <= newEndIdx && oldStartIdx <= oldEndIdx) {
    console.log(`newStartIdx：${newStartIdx}，newEndIdx：${newEndIdx}`);
    console.log(`oldStartIdx：${oldStartIdx}，oldEndIdx：${oldEndIdx}`);
    if (!oldCh[oldStartIdx]) {
      oldStartIdx++;
    }
    if (!oldCh[oldEndIdx]) {
      oldEndIdx--;
    }
    if (judge(oldCh[oldStartIdx], newCh[newStartIdx])) {
      console.log('命中新前和旧前');
      patchVnode(newCh[newStartIdx], oldCh[oldStartIdx]);
      newStartIdx++;
      oldStartIdx++;
    } else if (judge(oldCh[oldEndIdx], newCh[newEndIdx])) {
      console.log('命中新后与旧后');
      patchVnode(newCh[newEndIdx], oldCh[oldEndIdx]);
      newEndIdx--;
      oldEndIdx--;
    } else if (judge(oldCh[oldStartIdx], newCh[newEndIdx])) {
      console.log('命中新后与旧前');
      patchVnode(newCh[newEndIdx], oldCh[oldStartIdx]);
      parentElm.insertBefore(oldCh[oldStartIdx].elm, oldCh[oldEndIdx].elm.nextSibling);
      newEndIdx--;
      oldStartIdx++;
    } else if (judge(oldCh[oldEndIdx], newCh[newStartIdx])) {
      console.log('命中新前与旧后');
      patchVnode(newCh[newStartIdx], oldCh[oldEndIdx]);
      parentElm.insertBefore(oldCh[oldEndIdx].elm, oldCh[oldStartIdx].elm);
      newStartIdx++;
      oldEndIdx--;
    } else {
      console.log('都没命中');
      if (!mp) {
        mp = new Map();
        for (let i = oldStartIdx; i <= oldEndIdx; i++){
          mp.set(oldCh[i].key, i);
        }
      }
      let oldVnodeIdx = mp.get(newCh[newStartIdx].key);
      if (oldCh[oldVnodeIdx]) {
        patchVnode(newCh[newStartIdx], oldCh[oldVnodeIdx]);
        parentElm.insertBefore(oldCh[oldVnodeIdx].elm, oldCh[oldStartIdx].elm);
        oldCh[oldVnodeIdx] = undefined;
      } else {
        parentElm.insertBefore(newCh[newStartIdx].elm, oldCh[oldStartIdx].elm);
      }
      newStartIdx++;
    }
  }
  if (newStartIdx <= newEndIdx) {
    for (let i = newStartIdx; i <= newEndIdx; i++){
      parentElm.insertBefore(createElement(newCh[newEndIdx]), oldCh[oldStartIdx]);
    }
  } else if (oldStartIdx <= oldEndIdx) {
    for (let i = oldStartIdx; i <= oldEndIdx; i++){
      if(oldCh[i]) parentElm.removeChild(oldCh[i].elm);
    }
  }
}

github源码地址

手写虚拟dom和diff算法